题解 | #数的划分#

数的划分

http://www.nowcoder.com/practice/24c2045f2cce40a5bf410a369a001da8

题意：

将整数n划分成k份，每份不能为空，求划分的种数。

方法一：回溯法

解题思路：

分析数划分的规律，n=7，k=3，如图：
根据上图我们总结一下此种划分的规律：
（1）右边的数大于等于左边的数
（2）每一个位置都是从最小可能的数开始增加到最大可能的数。
因此按照这种规律可以保证划分的唯一性和完备性。
使用深度优先遍历和回溯法的思想来解决本题：用数组nums存储划分的值，辅助函数helper是实现深度优先和回溯，按照上述的规律实现，增加回溯时的剪枝条件left>=nums[cur-1]和i<=left/(k-cur)以减少搜索深度，去掉不必要的搜索。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int ans=0;
    int divideNumber(int n, int k) {
        // write code here
        //nums存储划分的值
        vector<int> nums(k);
        int cur=0,left=n;
        helper(nums,cur,left,k);
        return ans;
    }
    //实现回溯法的辅助函数
    void helper(vector<int>&nums,int cur,int left,int k){
        //满足方案条件
        if(cur==k-1&&left>=nums[cur-1]){
            ans++;
            return;
        }
        //剪枝一
        if(left<nums[cur-1])
            return;
        //边界条件，当cur==0时，初始化i为1
        int i=cur>0?nums[cur-1]:1;
        //剪枝二:i<=left/(k-cur) 
        for(;i<=left/(k-cur);i++){
            //回溯法主体
            nums[cur]=i;
            helper(nums,cur+1,left-i,k);
            nums[cur]=i;
        }
    }
};

复杂度分析：

时间复杂度： $图片说明$ ， $图片说明$ 是对划分结果的组合遍历时间复杂度，O(k)是求每个划分结果时的时间复杂度，因此每个划分都是k个数组成。
空间复杂度： $O(k+n)$ ，额外数组空间nums,O(k),递归栈空间O(n)。

方法二：动态规划

解题思路：

分配一个(n+1)*(k+1)的数组dp，默认值为0，dp[i][j]表示将数i划分为j份的可能数。有如下递推关系：
dp[i][j]=dp[i-1][j-1]+dp[i-j][j]
将dp[i][j]分成两种可能，（1）j个数中存在至少一个1，则这部分数为从将数i-1划分为j-1份的可能数dp[i-1][j-1] （2）j个数中全部大于1，则将所有数减一，那么这部分数为将数i-j划分为j份的可能数dp[i-j][j]，当然会有i-j<j的情况，默认值为0。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int divideNumber(int n, int k) {
        // write code here
        //二维数组dp (n+1)*(k+1)
        vector<vector<int>> dp(n+1,vector<int>(k+1));
        int mod=1000000007;
        cout<<mod<<endl;
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                //递推更新dp[i][j]，代表将i分成j份的划分数
                if(i>=j)
                    dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%mod;
            }
        }
        //返回结果
        return dp[n][k];
    }

};