web analytics

OpenJudge 666:放苹果 // 瞎基本DP

666:放苹果

总时间限制: 
1000ms    
内存限制: 
65536kB
描述
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
样例输出

分析:

放苹果,仔细看,恩递推,再仔细看,好像没有固定的套路.但是又想想好像好几种套路都可以解决掉.所以这里讲几种方法

P1:记忆化DP方式:

我们考虑,我们用i个苹果放在j个盘子里有几种方式呢.

1,我们可以空一个盘子,之后i个苹果,放在j个盘子里

2,我们可以将每个盘子里都放1个苹果,接下来的i-j个苹果可以放在j个盘子里.

而这个思路,其实状态转移方程就是可以写出来了.

这里会有点小问题可能需要解释一下.

1,可能会想到,为什么我们不能在一个状态里空好几个盘子呢..每次都考虑过放盘子.而转移到当前状态的时候.是考虑过前面空盘子的状态.所以这里就考虑一个位置的情况就行了.
2,初始化的问题.这里我们想到.如果我们就没有盘子,但是有很多苹果,其实就一种情况.反过来如果就一个苹果但是有很多盘子,这里也就只有一种情况.所以这里边界其实就显而易见就出来了.

2,背包DP解法

这种解法其实正确来讲用i来表示到底有多少个盘子是空的.而每次如果是空的.那就相当与在j-1个盘子里放k-i个苹果.这里的每一种状态的方案数是其他方案综合起来的.所以这个会简单一点.

所以这里最好是根据代码来理解每一个状态之间的转移.

Post a Comment

You must be logged in to post a comment.