Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
1 7 3
Sample Output
8
解题：由题可知，每个盘子都一样，可以任意放，要不能重复种数，那么可以这样假设：设1到n个盘子放平果的数量为a1,a2,a3,......,an.并且a1+a2+a3+.....+an=sum(平果总数)。如果a1<=a2<=a3<=.....<=an,即a(n-1)<=an.这样就不会重复。现在关建在于第i个盘最多放多少个平果。设第i个盘最多放maxi个平果，那么maxi=sum/(n-i);这样都搞定之后，用dfs确定每个盘放平果的数量，当都满足a(n-1)<=an时，就算是一种。把满足条件的种数加起来就是n个盘放sum个平果的种数。
dfs:
#include<stdio.h> int max[15],n,m;//n盘子数，m为平果数 void setmax()//计算每个盘最多放多少个 { for(int i=0;i<n;i++) max[i+1]=m/(n-i); } int dfs(int sum,int p,int v)//sum为放好的平果数，p是第v-1个盘放的平果数 { int ans=0; if(v==n&&m-sum>=p)//m-sum是用在第n个盘放的平果 return 1; if(v==n) return 0; for(int s=p;s<=max[v];s++)//从p开始，满足a(v-1)<=a(v). ans+=dfs(sum+s,s,v+1); return ans; } int main() { int t,ans[15][15]={0}; scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); setmax(); if(ans[n][m]==0) ans[n][m]=dfs(0,0,1); printf("%d\n",ans[n][m]); } }
递推：#include<stdio.h> int ans[11][11][11]={0};//从左到右维数分别代表 n盘子数，m平果数,第n个盘放j个平果 int main() { int t,n,m,i,j,dp[11][11]; for(n=1;n<=10;n++)//盘子数 for(m=1;m<=10;m++)//平果数 { dp[n][m]=0; if(m==1||n==1) { ans[n][m][m]=1; dp[n][m]=1;continue; } for(j=0;j<=m/n;j++)//第n个盘放j个平果 { for(i=j;i<=m/(n-1);i++)//第n-1个盘放i个平果 ans[n][m][j]=(ans[n][m][j]+ans[n-1][m-j][i]); dp[n][m]=(dp[n][m]+ans[n][m][j]);//n个盘放m个平果有dp[n][m]种放法 } } scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); printf("%d\n",dp[n][m]); } }