作为一名小白，完全不知道动态规划究竟是什么意思，百度了下词条我语文不好看不懂它在说什么，那不如联系下实际，看看动态规划算法究竟怎么用。来自杭电oj1028题 昨天按照自己的理解，将网上抄的代码按照递归来理解，今早女神发信息说这是动态规划，递归是函数自己调用自己，一看果然不是递归，大体思路没啥太大问题，那也重新理解下： 以下是我昨天对于这道题的理解：
拿到这道题，我们不妨转变思路，把此题转变成n个苹果装入n个盘子的过程，我们需要两个变量i,j分别代表苹果数和盘子数，由于ij需要进行循环，且苹果作为大循环，盘子作为小循环，大循环嵌套小循环，所以我们定义一个二维数组来形象的存储苹果和盘子，最后将本身的值作为我们想要的结果——有几种摆放方法。接下来我们要考虑苹果和盘子的数量关系：
盘子数大于苹果数：很简单将问题转化成将苹果放入和苹果数量等同的盘子中即可。盘子数等于苹果数：根据题中示例，可明了的将问题转化为将苹果放入盘子数-1的盘子中的所有情况加一盘子数小于苹果数：又得分两种情况第一种情况是填完苹果之后还有空余盘子，第二种情况就是盘子都填满了；第一种情况的话，如果填完之后还有空余盘子，那就可以把那个空的盘子（至少有一个）拿走，所以减一最后总的情况数还是不变的，第二种情况的话，如果都填满了，那么我们把每一个盘子都拿走一个苹果之后，他的这种情况应该和没拿之前那种情况是一样的，其实我有这地方有点儿想不太懂，我拿笔写了一下，一下子懂了，所以年轻人遇到问题一定要多动笔。 上面第二条分析很不清楚，今早看了女神给我发的信息，正确的理解应该是当苹果数i=盘子数j 时， 分两种情况讨论： 1、至少有一个盘子不放苹果，摆放方式就是把i 个苹果放在j-1个盘子里(摆放方式总数与第一个空盘子无关)，摆放方式总数表示为dp[i][j-1] 2、每个盘子都放苹果，因为苹果数=盘子数，所以刚好每个盘子一个苹果，只有一种摆放方式 故当盘子数等于苹果数的代码为：dp[i][j]=1+dp[i][j-1];再系统说下本题，及需要注意的点：
dp[a][b]
表示把a 个苹果放入b 个盘子的摆放方式总数，允许有的盘子不放苹果，画一个类似棋盘的表格，例如第一行第五列的小格，表示把五个苹果放在1个盘子里，小格里面填写对应的摆放方式的总数；需要注意的点：
动态规划的第一个难点是，设置递推公式的初始状态。很好理解，如果斐波那契数列不给出数列的第一个数和第二个数，这个数列的其余的数不能根据递推公式计算出来 这个题，设置初始状态的语句对应的是 dp[1][j]=dp[i][1]=1;这个循环动态规划的第二个难点是，让dp数组的下标还有数组元素的值分别表示什么意义 这道题里，就是：dp[a][b]表示把a 个苹果放入b 个盘子的摆放方式总数，允许有的盘子不放苹果第三个难点找到递归关系（不要落情况） 代码如下： #include<stdio.h> int dp[121][121]; int main() { int i,j; int n; for (i=1;i<=121;i++) dp[1][i]=dp[i][1]=1; for (i=2;i<121;i++) { for (j=2;j<=121;j++) { if (i<j) dp[i][j]=dp[i][i]; else if (i==j) dp[i][j]=1+dp[i][j-1]; else if (i>j) dp[i][j]=dp[i-j][j]+dp[i][j-1]; } } while( scanf("%d",&n)!= EOF ) { printf( "%d\n" , dp[n][n]); } return 0; }