题目描述
将整数nn分成kk份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
例如：n=7n=7，k=3k=3，下面三种分法被认为是相同的。
1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.
问有多少种不同的分法。
输入输出格式
输入格式：
n,kn,k (6<n \le 2006<n≤200，2 \le k \le 62≤k≤6)
输出格式：
11个整数，即不同的分法。
输入输出样例
说明
四种分法为：
1,1,51,1,5;
1,2,41,2,4;
1,3,31,3,3;
2,2,32,2,3.
用dfs很简单：
#include<cstdio> int n,k,cnt; void dfs(int last,int sum,int cur)
{
if(cur==k)
{
if(sum==n) cnt++;
return;
}
for(int i=last;sum+i*(k-cur)<=n;i++)//剪枝，只用枚举到sum+i*(k-cur)<=n为止
dfs(i,sum+i,cur+);
} int main()
{
scanf("%d%d",&n,&k);
dfs(,,);
printf("%d",cnt);
}
dp[i][j]代表数i被分成j份的数量
转移方程
主要分为 有1 和无1 这两种就包含了所有的情况了！！！！！！
有1 （分出一个1 即可） dp[i][j]=dp[i-1][j-1];
重点是无1 ：
dp[i][j]=dp[i-j][j] 意为 给后面dp[i-j][j]每个数字加上1即可了 保证了无1
还有就是注意边界处理
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 1500+5
int dp[N][N];
int main()
{
int n,k;
RII(n,k);
rep(i,,n)
dp[i][]=; rep(i,,n)
rep(j,,k)
if(i>j)
dp[i][j]=dp[i-][j-]+dp[i-j][j];
else dp[i][j]=dp[i-][j-]; cout<<dp[n][k];
return ;
}