算法训练 数的划分
时间限制：1.0s 内存限制：256.0MB
锦囊1
使用动态规划。
锦囊2
用F[i,j,k]表示将i划分成j份，最后一份为k的方案数，则F[i,j,k]=sum F[i-k,j-1,k']。其中k'
问题描述
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入格式
n，k
输出格式
一个整数，即不同的分法
样例输入
7 3
样例输出
4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
数据规模和约定
6<n<=200，2<=k<=6
注释：用的递归，不过上一道题记得超时来着，在这里又过了，怪哉。
/*
分析：递归问题。
step表示当前剩余的数需要分成的份数;把n分成k份，
只需第一个数等于i，计算从i等于1一直到i等于n/k,然后
把剩余的n-i分成k-1份的种类数.
front为剩余的要划分的数的前一个数，每次i从front
开始一直到n/step结束，这样才能保证得到的划分方式是
不递减的，才能保证不会有重复的情况产生.
*/
#include<stdio.h>
#include<string.h>
int ans=;
void dfs(int front, int n, int step){
if(step==){
ans++;
return;
}
for(int i=front; i<=n/step; i++){
dfs(i, n-i, step-);//i一直是front;n-i表完成一次划分后剩下的
}
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
/*1循环到n：代表将n划分为1到n的各个份数*/
// for(int i=1;i<=n;i++){
// dfs(1,n,i);
// }
/*不循环：指定了划分份数k*/
dfs(,n,k);
printf("%d",ans);
return ;
}