数的划分之动态规划

1.对应OJ链接：

数的划分_牛客题霸_牛客网 (nowcoder.com)

2.题目描述：

3.解题思路：

方法一：直接暴力递归

 

从index位置开始进行尝试一直到n,具体请看代码。 

对应代码：

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int divideNumber(int n, int k) {
        // write code here
        return process(n, k, 1);
    }
    //递归含义:从index位置开始将n划分成k分的方法数
    int process(int n, int k, int index) {
        if (k < 0) {
            return 0;
        }
        //如果剩下了0分那么只有当k为0时有一种划分结果
        if (k == 0) {
            return n == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int i = index; i <= n; i++) {
            //尝试i位置上的数
            ways += process(n - i, k - 1, i);
        }
        return ways;
    }
};

但是很不幸的是这种方法即使改成记忆化搜索和dp依然会超时。下面我们来看下面一种方法。感觉特别的妙：

 我们可以将k想象成有k个盒子按照题目的意思就是每个盒子不能为空，那么我们可以提前给每个盒子都放入一个1这样一来盒子就不会是空的了。然后我们再将剩下的n-k个小球再放到k个盒子里面即可，此时就有多种可能性了 n-k个小球可以放到第一个盒子中，可以放到1和2这两个盒子当中也可以放到1到3这三个盒子当中，也可以放到1到k这些盒子当中。

对应代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    vector<vector<int>>dp;
    int mod=1000000000+7;
    int divideNumber(int n, int k) {
        // write code here
      //  dp.resize(n+1,vector<vector<int>>(k+1,vector<int>(n+1,-1)));
        dp.resize(n+1,vector<int>(k+1,-1));
        return process(n,k);
    }
    //将n划分成k分的方法数
    int process(int n,int k)
    {
        if(n==k){
            return 1;
        }
        if(k>n){
            return 0;
        }
        
        if(dp[n][k]!=-1){
            return dp[n][k];
        }
        int ways=0;
        //剩下的n-k个小球放到k个盒子里面的可能性进行枚举
        for(int i=1;i<=k;i++){
            ways=(ways+process(n-k,i))%mod;
        }
        dp[n][k]=ways;
        return ways;
    }
};

斜率优化：

 对应代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    vector<vector<int>>dp;
    int mod=1000000000+7;
    int divideNumber(int n, int k) {
        // write code here
      //  dp.resize(n+1,vector<vector<int>>(k+1,vector<int>(n+1,-1)));
        dp.resize(n+1,vector<int>(k+1,-1));
        return process(n,k);
    }
    //将n划分成k分的方法数
    int process(int n,int k)
    {
        if(k==0){
           return n==0?1:0;
        }
        if(k==n){
            return 1;
        }
        if(k>n){
            return 0;
        }
        if(dp[n][k]!=-1){
            return dp[n][k];
        }
        int ways=process(n-1,k-1);
        ways=(ways+process(n-k,k))%mod;
        dp[n][k]=ways;
        return ways;
    }
};