题解 | #数的划分#
数的划分
http://www.nowcoder.com/practice/24c2045f2cce40a5bf410a369a001da8
数的划分
问题描述：将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5;
1，5，1;
5，1，1;
问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
输出：一个整数，即不同的分法。
示例
输入：7,3
返回值：4
说明：整数7分为3份有4种办法:[1,1,5][1,2,4][1,3,3][2,2,3]
方法一
思路分析
使用动态规划的办法进行分析，本题可以类比将$n$个小球放入$k$个盒子中，小球、盒子无差别，且盒子不能为空。设置将$n$个小球放入$k$个盒子中方法为$f[n][k]$，因此为了使每个盒子中不为空，先拿出$k$个小球分别分别放到每个盒子中，再将$n-k$个小球放入$k$个盒子中，其方法数为$f[n-k][k]$；或者保证每个盒子至少有一个小球，先将1个小球放入1个盒子中，剩余的$n-1$个小球放入$k-1$个盒子中其方法数为$f[n-1][k-1]$，因此总的方法数为$f[n][k]= f[n-k][k]+ f[n-1][k-1]$。具体步骤如下：
- 设置$f[n][k]$为整数$n$分成$k$份，且每份不能为空的方法数
- 其转移方程为$f[n][k]=f[n-k][k]+f[n-1][k-1]$
- 初始化$f[0][0]=1$，只有当$n$大于等于$k$才可进行划分。
状态转移方程：
图解
输入：5，3
返回值：2
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 被划分的数
* @param k int 化成k份
* @return int
*/
int mod=1000000007;
int divideNumber(int n, int k) {
// write code here
if(n<k) return 0;
vector<vector<int>> f(n+1,vector<int>(k+1));
f[0][0]=1;//初始化
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(i>=j)//类比小球数量必须大于盒子数量k
f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
}
}
return f[n][k];
}
}; 复杂度分析
- 时间复杂度：设置内外两层嵌套循环，外层循环次数为$n$，内层循环次数$k$，因此总的时间复杂度为$O(n*k)$
- 空间复杂度：借助于一个二维数组$f[n][k]$用于存放整数$n$分成$k$份，且每份不能为空的方法数，因此空间复杂度为$O(n*k)$
方法二
思路分析
直接采用暴力搜索的办法，对于一个整数，首次分配我们可以分配1，2，...，接着如果选定第一次分配1，那么第二次可以分配1，2，...，一直往下，直到所有的分配数之和为整数n，分配次数为k，此时这是一种分配的方案数。
图解
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 被划分的数
* @param k int 化成k份
* @return int
*/
int depth;
int sum;//存储划分方案数
int divideNumber(int n, int k) {
// write code hereif
depth=k;
sum=0;
if(n<k) return 0;
search(0,n,1);//第一个参数表示搜索的深度层数，第二个参数表示整数n的剩余数，第三个参数表示分配数开始的数，由于不能为空，因此开始为1
return sum;
}
void search(int dep,int res,int start)
{
if(dep==depth+1)
{
if(res==0)//整数n已经分配完成，是一种分配方案
sum++;
return;
}
for(int i=start;i<=res;i++)//继续向下搜索，并且层数+1，n剩余的数需要减去开始的数
{
search(dep+1,res-i,i);
}
}
}; 复杂度分析
- 时间复杂度：将整数$n$分为$k$个，且每个不能为空，可类比为将$n$个小球使用挡板隔开，挡板数为$k-1$，需要的操作为
，因此时间复杂度为
- 空间复杂度：每次递归的空间为$O(1)$，共递归$k$次，因此空间复杂度为$O(k)$
