题解 | #数的划分#

题目描述
将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5;
1，5，1;
5，1，1;
问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
输出：一个整数，即不同的分法。

方法一：递归求解

求解思路
对于本题目要求将整数n分成k份的个数，我们使用递归的思想进行解答。首先我们明确递归的终止条件为分成了k份。然后递归进行推进，当份数加1时，我们设置rest和use两个变量，其中rest减去已经分配的数字，use则是当前尝试分配的数字，根据上述描述，最终求出题目的答案即可。

解题代码

import java.util.*;
public class Solution {
    int k;
    int count; // 存储分类数
    public int divideNumber (int n, int k) 
    {   //初始化k和cnt
        this.k=k;
        this.count=0;
        dfs(0,n,1); // 开始递归
        return count; // 返回结果
    }
    private void dfs(int depth,int rest,int use)
    {   //如果达到k份，递归终止
        if(depth==k)
        {
            if(rest==0)
            {
                count++;
            }
            return;
        }
        for(int i=use;i<=rest;i++)
        {
            dfs(depth+1,rest-i,i);
        }
    }
}

复杂度分析
时间复杂度：将数n分成k份，即看成n个1，在n-1个空格中放入k-1个挡板，并且不需要考虑其顺序。因此时间复杂度为( )
空间复杂度：使用深度为k的递归栈，因此空间复杂度为

方法二：动态规划--优化求解

求解思路
对于本题目我们也可采用动态规划的思想来进行求解，其中dp[i][j]表示数字i分成j份总共有多少种分法。并且置初值dp[0][0] = 1.对于状态转移过程，我们分为两种情况进行讨论，一种是至少有一份分配了数字1，另一种是没有分配数字1.那么如果至少分配了一份是数字1，那么剩下的分发就是dp[i-1][j-1],即将数字i-1分为j-1.如果没有分配数字1，那么我们一定可以将j份都提前放一个数字1，剩下的就是dp[i-j][j]，即将数字i-j分为j份，因此我们根据上述想法，写出转移方程为dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%mod

解题代码

import java.util.*;
public class Solution {
    public int divideNumber (int n, int k) {
        int[][] mydp=new int[n+1][k+1]; // 初始化数组
        mydp[0][0]=1; // 赋初值
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {   //由于每份不能为空，所以划分数肯定大于总份数
                if(i>=j)
                {   //分为至少存在一份是1，和所有份数大于1两种情况
                    mydp[i][j]=(mydp[i-1][j-1]+mydp[i-j][j])%1000000007; // 状态转移方程
                }
            }
        }
        return mydp[n][k]; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环，因此时间复杂度为( )
空间复杂度：需要引入额外的dp数组，因此空间复杂度为,其中k为份数。