放苹果问题 DP计数 m个苹果放在n个盘子里，苹果，盘子相同，盘子可为空

详细的解释放苹果问题的链接：苹果可相同可不同，盘子可相同可不同，盘子可空和不可空，都有详细的说明···

http://www.cnblogs.com/celia01/archive/2012/02/19/2358673.html

不赘述：这里的代码是递归，记忆化搜索，避免重复计算某些数的值```

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 50
 4 int d[N][N];
 5 int dfs(int x,int y)//x个苹果放入y个盘子中的放法数
 6 {
 7     if(d[x][y] != -1) return d[x][y];
 8     if(x<0) return 0;//苹果个数小于0
 9     if(x==0 || y == 1) return 1;//苹果个数等于0或者盘子个数等于1
10     return d[x][y] = dfs(x-y,y)+dfs(x,y-1);//每个盘子都不为空||至少一个盘子为空
11     //每个盘子都不为空的方法相当于苹果个数x-n，y个盘子的放法····
12 }
13 int main()
14 {
15 //    freopen("in.c","r",stdin);
16     int t;
17     scanf("%d",&t);
18     memset(d,-1,sizeof(d));
19     while(t--)
20     {
21         int m,n;
22         scanf("%d%d",&m,&n);
23         printf("%d
",dfs(m,n));
24     }
25     return 0;
26 }

View Code

还有二维DP类的

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 50
 4 //#define debug
 5 int d[N][N];
 6 void init()
 7 {
 8     for(int i=0; i<N; ++i)
 9         d[0][i] = d[1][i]=d[i][0]=d[i][1] =1;
10     for(int i=2; i<N; ++i)
11     {
12         for(int j=2; j<N; ++j)
13         {
14             if(i-j >= 0) d[i][j] += d[i-j][j];
15             d[i][j] += d[i][j-1];
16         }
17     }
18 #ifdef debug
19     for(int i=2; i<=7; ++i)
20     {
21         for(int j=2; j<=7; ++j)
22         {
23             printf("%d  ",d[i][j]);
24         }
25         puts("");
26     }
27 #endif
28 }
29 int main()
30 {
31 #ifdef debug
32     freopen("in.c","r",stdin);
33 #endif
34     init();
35     int t;
36     scanf("%d",&t);
37     while(t--)
38     {
39         int m,n;
40         scanf("%d%d",&m,&n);
41         printf("%d
",d[m][n]);
42     }
43 
44     return 0;
45 }

View Code