题解 P1025 【数的划分】
这道题有两个思路
第一个是递归：
为了确保出现过的方案不重复，
可以规定在后面的分组中的数必须要大于前面分组中的数，
x代表上一个出现过的数，初值为1，只要让下一个数从x开始循环，便可达成上述方案。
s代表还需多少次递归，初值为k，递归k次，即分为k组后便可退出循环。
t代表到此次还剩多大的数可以分，初值定为n。
同时循环最大只能进行到t/s，
避免出现因前面的数过大而导致后面的数无法取的情况。
代码如下：
#include<cstdio>
using namespace std;
int sum;
void dfs(int x,int s,int t)
{
if(s==1)
{
sum++;
return;
}
for(int i=x;i<=t/s;i++)
dfs(i,s-1,t-i);
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
dfs(1,k,n);
printf("%d",sum);
return 0;
}第二个是递推： solution【i】【j】代表在数的和为i的情况下分为j组共有的情况数。
由于无论在数的和为几时，把它们分成0组都是0种情况，分成一组都是一种情况，
所以j=0时全部要初始化为0，j=1时全部要初始化为1。
同时，无论共分为几组，数的和为0和1是0种情况（i=j=1除外）
所以i=0或i=1时j从2开始全部初始化为0。
对于剩下的任意一个solution【i】【j】，都可以用如下方式求得：
solution【i】【j】=第一个数为1的所有情况+第一个数不为1的所有情况。
第一个数为1时，1占用了1个位置和占用了总数中的1是已经确定了的，
因此，第一个数为1的所有情况=solution【i-1】【j-1】。
第一个数不为1时，可以视为先在所有的位置上都加上一个1再对于所有的位置用新的总数求次数，
所以定了的是占有了总数j个，位置仍然是j个，与原来相比没有变化。
因此，第一个数不为1的所有情况=solution【i-j】【j】。
所以solution【i】【j】=solution【i-1】【j-1】+solution【i-j】【j】。
代码如下：
#include<cstdio>
using namespace std;
int main()
{
int solution[205][10];
int n,k,i,j;
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++)
{
solution[i][1]=1;
solution[i][0]=0;
}
for(i=2;i<=k;i++)
{
solution[1][i]=0;
solution[0][i]=0;
}
for(i=2;i<=n;i++)
for(j=2;j<=k;j++)
if(j>i)
solution[i][j]=0;
else
solution[i][j]=solution[i-1][j-1]+solution[i-j][j];
printf("%d",solution[n][k]);
return 0;
}