题目大意
把整数n分成k份，每份都不能为空，任意两种方案都不相同（不考虑顺序，即1、1、5；1、5、1；5、1、1这三种方案是相同的）。求把整数n分为k份的方案数
题目分析
设f(i,j)表示把i分为k份时的方案数：
明显看出，当i<j时，f(i,j)==0；
当i==j时，也只有每份都为1一种分法，所以f(i,j)==1；
当i>j时，有两种情况：
1、j份中有至少一份为1，则方案数与将整数i-1分为j-1份时是一样的，所以有1的情况的方案数==f(i-1,j-1)
2、j份中没有1时，则将j份每一份都减去1，所以方案数为f(i-j,j)；
综上，f(i,j)==f(i-1,j-1)+f(i-j,j)；
Code
#include<iostream> #include<cstdio> #define sco 100 using namespace std; int n,m,f[sco][sco]; int main(){ scanf("%d%d",&n,&m);f[1][0]=1; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j){ if(j==1)f[j][i]=f[j+1][i-1]+f[n][i-1]; else if(j==n) f[j][i]=f[1][i-1]+f[j-1][i-1]; else f[j][i]=f[j+1][i-1]+f[j-1][i-1]; } printf("%d",f[1][m]); return 0; }