1039 数的划分

题目链接：http://codevs.cn/problem/1039/
题目描述 Description
将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的分法。

输入描述 Input Description
输入：n，k (6<n<=200，2<=k<=6)
输出描述 Output Description
输出：一个整数，即不同的分法。
样例输入 Sample Input
7 3
样例输出 Sample Output
4
输入输出样例说明：四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;

算法分析：
本题类似于放苹果这道题。 但是放苹果这道题可以有盘子为空，这里不允许某一份是空的。所以，这里讨论时以拆分结果是否包含1为主要的讨论点。

另外一定要注意区分简单的整数划分这道题。那道题是把n拆分为若干个正整数之和，个数不限制。这里限制拆分为k个。

设f(n,k)为整数n拆分成k个数字的方案数，则可以分以下两种情况讨论。
(1)拆分的结果不包含1的情况：如果不包含1，我们把n拆分成k块时可以看做先将每一块加上个1，则n还剩余n-k，即f(n-k,k)
(2)拆分的结果包含1的情况：那么就直接选一个1，即f(n-1,k-1)。

那么总递推式为 f(n,k)=f(n-k,k)+f(n-1,k-1)
这里还要判断递归终止情况：
(1)n=0或n<k或k=0时，方案数为0。(其实k每次最多减少1，总会遇到k==1的情况，所以k==0可以忽略。但考虑到可能输入特殊测试样例的情况，可以保留该条件.)
(2)k=1或k=n时方案数为 1。

 1 #include<stdio.h>
 2 
 3 int fun(int n,int k) 
 4 {
 5     if(n==0||n<k||k==0)return 0;
 6     else if(n==k||k==1) return 1; 
 7     else return fun(n-k,k)+fun(n-1,k-1);
 8 }
 9 
10 int main()
11 {
12     int n,k;
13     scanf("%d%d",&n,&k);
14     printf("%d\n",fun(n,k));
15 }

 以下代码参考：http://blog.csdn.net/noip123/article/details/54782826

 1 #include<cstdio>  
 2 using namespace std;  
 3 int n,k,d[205][8];  
 4 int main()  
 5 {  
 6     scanf("%d%d",&n,&k);  ///把n整数划分成k份  
 7     d[0][0]=1;            //边界  
 8     for(int i=1;i<=n;i++)  
 9       for(int j=1;j<=i&&j<=k;j++)  //划分次数不能超过数本身，也不能超过求的划分次数  
10         d[i][j]=d[i-1][j-1]+d[i-j][j];  //递推计算  
11     printf("%d\n",d[n][k]);  
12     return 0;  
13 }  

DP递推

 1 #include<iostream>  
 2 using namespace std;  
 3 int dfs(int n,int k)  //把n整数划分成k份  
 4 {  
 5     if(n==0||n<k||k==0)return 0;  //无法继续划分  
 6     if(k==1||n==k)return 1;       //只能划分成一项  
 7     return dfs(n-1,k-1)+dfs(n-k,k);  
 8 }  
 9 int main()  
10 {  
11     int n,k;  //把n整数划分成k份  
12     cin>>n>>k;  
13     int x=dfs(n,k);  
14     cout<<x<<"\n";  
15     return 0;  
16 }  

DFS递归