poj 1664 放苹果
http://poj.org/problem?id=1664
一道基础的题目，dp[i][j]代表 i 个苹果 放到 j 个盘子的总类数目。
dp[ i ][ j ] = dp[ i ] [j -1 ] + dp[ i -j ][ j ];
分类讨论第j个盘子是否放了苹果。
没有放的时候 dp [ i ][ j-1 ]种，把i个苹果全部放在前 j -1 个盘子里；
放的时候，可能是放一个，可能是放多个，也就说我可以这样转化，先在所有的盘子上放上一个，然后，任意放。
即dp[ i - j ] [ j ].
1 #include<stdio.h> 2 3 int dp[11][11]; 4 void prepare() 5 { 6 int i,j; 7 // put i apples into j pans. 8 9 for(i=0;i<=10;i++) dp[0][i]=1; 10 for(i=1;i<=10;i++) 11 { 12 for(j=1;j<=10;j++) 13 if(j<=i) 14 dp[i][j]=dp[i][j-1]+dp[i-j][j]; 15 else 16 dp[i][j]=dp[i][j-1]; 17 } 18 } 19 int main() 20 { 21 int T; 22 int n,m; 23 prepare(); 24 scanf("%d",&T); 25 while(T--) 26 { 27 scanf("%d%d",&n,&m); 28 printf("%d\n",dp[n][m]); 29 } 30 return 0; 31 }
hdu 2512
一卡通大冒险
也是一道基础的题目。
dp[ i ] [ j ] 代表 i 个东西分成 j 个集合的方法数。
也对第j 个元素进行讨论。
dp[ i ] [j ] = dp [ i -1 ] [ j -1 ] + j* dp[ i -1][ j ];
方法同上，唯一不同在于 集合中没有排序。
1 #include<stdio.h> 2 #include<string.h> 3 4 int dp[2001][2001]; 5 void prepare() 6 { 7 int i,j; 8 dp[1][1]=1; 9 for(i=2;i<=2000;i++) 10 for(j=1;j<=i;j++) 11 dp[i][j]=(dp[i-1][j-1]+j*dp[i-1][j])%1000; 12 } 13 int main() 14 { 15 int T; 16 int n,i,cur; 17 scanf("%d",&T); 18 prepare(); 19 while(T--) 20 { 21 scanf("%d",&n); 22 cur=0; 23 for(i=1;i<=n;i++) 24 cur=(cur+dp[n][i])%1000; 25 printf("%d\n",cur); 26 } 27 return 0; 28 }
原文：http://www.cnblogs.com/tom987690183/p/3654579.html
