数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。

输入输出格式

输入格式：

 

n，k (6<n<=200，2<=k<=6)

 

输出格式：

 

一个整数，即不同的分法。

 

输入输出样例

输入样例#1： 7 3 输出样例#1： 4

说明

四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;

 

思路

f[i][j]是指将i划分成j部分的方案数初始化f[0][0]=1f[i][j]有意义（i>=j）的情况下满足公式f[i][j]=f[i-1][j-1]+f[i-j][j]

解释：

有一种情况是分离出一个1，那么剩余的i-1就只能划分成j-1个部分，由于是地推，所以划分结果中有一个1，两个1，直到最大限度数量的1的情况全都囊括了以7 3为例 完全走这条路线的划分方式有5 1 1另外一种情况的讨论就是不包含1的结果了（对于最终答案）为了不包含1，就先把可能涉及1的情况都排除，也就是i-j完全走这条路线的划分方式有3 2 2

两条路线都走过的划分方式有4 2 13 3 1

 

思路：

这个题有两种做法

1.设n个物体分成m份则以下函数关系:

f(n,m)=0 m>n; f(n,m)=1 m=1; f(n,m)=0 m=0; f(n,m)=f(n-1,m-1)+f(n-m,m); /*法一，以函数关系为基础*/ #include<iostream> using namespace std; int n,k; int com(int x,int y) { if(y==1)return 1; if(x<y)return 0; if(x==0)return 0; return com(x-y,y)+com(x-1,y-1); } int main() { cin>>n>>k; if(n==k){cout<<1;return 0;} if(n<k){cout<<0;return 0;} cout<<com(n,k); } 法一，以函数关系为基础 #include<cstdio> #include<iostream> using namespace std; int f[500][10]; int main() { int n,k; cin>>n>>k; f[0][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) if(i>=j) f[i][j]=f[i-1][j-1]+f[i-j][j]; cout<<f[n][k]; return 0; } dp表现

2.直接爆搜，dfs加上极其强大的剪枝

/*法二，爆搜+剪枝*/ #include<cstdio> int n,m,ans=0; void dfs(int a, int b, int last) //last记录最大可取的值 { if (last*b < a) return; if (last*b == a) //刚好只有1组解 { ans++; return; } if (b == 1) //剪掉1层 { if (a!=0) ans++; return; } if (last > a) last=a; //可行性 if (last+b-1 > a) last=a-b+1; //可行性 for (int i=last; i>=1; i--) dfs(a-i,b-1,i); } int main() { scanf("%d%d",&n,&m); dfs(n,m,n); printf("%d",ans); return 0; } 法二，爆搜+剪枝