首页 > 试题广场 >

数的划分

[编程题]数的划分
  • 热度指数：4766 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将整数 n 分成 k 份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
例如： n=7,k=3 ，下面三种分法被认为是相同的。



问有多少种不同的分法, 答案对 109 + 7 取模。

数据范围： 
进阶：空间复杂度 ，时间复杂度
示例1

输入

7,3

输出

4
示例2

输入

6,2

输出

3
算法知识视频讲解
添加回答
Java
pein531头像 pein531

展示一下本平民对这道题的思考过程：暴力递归->动态规划->优化动态规划

1.暴力递归

由于统一组合的不同排列只算一种划分方式，因此这里我给定一个prev变量，表示上一次划分的值，本次划分值不能比它小，全力寻找递增的划分方案。先找到一种尝试模型进行暴力递归，代码如下： 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    public int divideNumber (int n, int k) {
        // write code here
        return recurrent(1, n, k);
    }
    
    /**
     * 分区调度，对模型按照复杂度划分为partition个工作量相近的分区
     * @param prev     前一个划分值
     * @param rest     目标数剩余部分
     * @param k        剩余划分数
     * @return         返回方法数
     */
    private int recurrent(int prev, int rest, int k) {
        if(rest == 0 && k == 0) {
            return 1;       // 剩余要凑的数没有了，形成一种方案
        }
        if(rest < prev || k < 0) {
            return 0;       // 剩余数为负数，或者没有划分操作次数了，当前划分方案失效
        }
        // 尝试当前可以划分出来的值，为了保持单调不减，需以从前一个数为下界
        int ways = 0;
        for(int i = prev; i <= rest; i++){
            ways += recurrent(i, rest - i, k - 1);
        }
        return ways;
    }
}
暴力递归仅用来形成一个思路，实际跑的话是会超时的，但我们根据递归的思路可以改出动态规划的版本。

2.动态规划

我们可以看到递归函数有3个可变参数，prev、rest和k，其中prev和rest的取值范围都是0~n，k的取值范围是0~k。因此知道这本质上是一个三维动态规划问题，需要准备一个(n+1)*(n+1)*(k+1)的三维dp数组来进行动态规划的求解。
  1. 而根据递归头的base case，我们可以知道对于任意的prev，只要rest和k归零，就有dp[prev][0][0]=1成立；
  2. 我们需要求的是dp[1][n][k]；
  3. 根据递归解第33~36行代码，我们可以知道一个普遍位置dp[prev][rest][k]依赖一系列的dp[i][rest-i][k-1]的值，而i需要进行枚举。如此一来可以确定填三维动态规划表的顺序为第一维rest从小到大，但受n的约束；第二维prev从小到大，但受rest的约束；第三维k由小到大，但受k的约束；最后还需要对i进行枚举，其上下界分别为rest和prev。一共有四层循环，复杂度仍然太高，还是会超时。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    public int divideNumber (int n, int K) {
        // write code here
        int[][][] dp = new int[n + 1][n + 1][K + 1];
        // 只要rest和k归零，就形成一种方案
        for(int prev = 1; prev <= n; prev++){
            dp[prev][0][0] = 1;
        }
        for(int rest = 1; rest <= n; rest++){
            for(int prev = 1; prev <= rest; prev++){
                for(int k = 1; k <= K; k++){
                    for(int i = prev; i <= rest; i++){
                        dp[prev][rest][k] += dp[i][rest - i][k - 1];
                    }
                }
            }
        }
        return dp[1][n][K];
    }
}
考虑到题中要求的时间和空间复杂度，再看看能不能删掉一些参数，从时间复杂度O(nk)来看，显然是不能删去k这个参数的。那么再想想rest和prev哪个可以删掉？考虑到某个数n拆分成k份，dp[n][k]会有两种情况：
  1. 如果当前拆了个1出来，那剩下n-1就需要拆成k-1块，可以从dp[n-1][k-1]拿值；
  2. 如果k块中一个1都没有，就相当于先给每个块分得一个1，然后剩下的n-k划分成k块与k块中已经有的那个1结合，可以从dp[n-k][k]中拿值。
因此变量prev可以删掉，抛弃划分结果单调性的设定。base case仍然是rest和k归零的情况下形成一种方案，得到状态转移方程：dp[n][k] = dp[n - 1][k - 1] + dp[n - k][k]，行列依赖的都是不超过自己的行列编号的值，因此正序遍历即可。这样就完成了时间复杂度和空间复杂度均为O(nk)的壮举。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    public int divideNumber (int n, int K) {
        // write code here
        int[][] dp = new int[n + 1][K + 1];
        dp[0][0] = 1;
        for(int rest = 1; rest <= n; rest++){
            for(int k = 1; k <= K && k <= rest; k++){
                dp[rest][k] = (dp[rest - 1][k - 1] + dp[rest - k][k]) % 1000000007;
            }
        }
        return dp[n][K];
    }
}

编辑于 2021-12-12 23:16:25 回复(4)
Java
唐氏综合征头像 唐氏综合征
大神解法：
1. 一定包含1，则剩余的部分只能从 i-1 数中拆分 j-1 出来，为 dp[i-1][j-1]
2. 一定不包含1， j 份都有可能包含1，因此包含1 的拆分的可能就是有 j 个，如果假设将拆分后的每部分都减去1，剩余的部分不管是否为1，在最后拆分的结果值上加1，每个部分就都大于1，因此需要找到每个部分都减去的状态，即对 i - j 进行拆分为 j份，再还原到 dp[i][j] 时，则可认为每个部分都大于1 , 所以 dp[i-j][j] 就是每个部分先减去1，找到所有的拆分可能，每个结果再+1 就是都不为1的情况。 
 public static int divideNumber(int n, int k) {
        final int MOD = (int) (Math.pow(10, 9) + 7); // 定义模数

        // 构建二维dp数组
        // dp[i][j] 表示将i拆分成j份的方案数
        int[][] dp = new int[n + 1][k + 1];

        // 初始化dp数组
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0; // 不能将i拆分成0份
        }
        for (int j = 0; j <= k; j++) {
            dp[0][j] = 0; // 不能将0拆分成j份
        }
        dp[0][0] = 1; // 将0拆分成0份只有1种方案

        // 动态规划填充dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (i >= j) {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % MOD;
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return dp[n][k];
    }

总结： 这道题的状态转移方程确实很难想到，我的思路是想从 dp[i-1][j] 和 dp[i][j-1] 上转移过来，但结果算多了

发表于 2024-07-05 16:06:37 回复(0)
C++
AsherChi头像 AsherChi 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int divideNumber(int n, int k) {
        // write code here
        int mod = 1e9+7;
        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
        for(int i=0; i<=k; i++)
        {
            dp[i][i] = 1;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=min(k, i); j++)
            {
                dp[i][j] = (dp[i-1][j-1] + dp[i-j][j]) % mod;
            }
        }
        return dp[n][k];
    }
};

发表于 2022-09-05 10:12:49 回复(1)
JavaScript
别卷啦！头像 别卷啦！

对于dp[i][j]代表i分为j份。分为以下两类：

  1. 每份都没有1：那么只需要将每份都减1然后保证有j份。即加上dp[i-j][j]。
  2. 至少有一份1：那么提出1个1,即加上dp[i-1][j-1]。 
    function divideNumber( n ,  k ) {
    // write code here
    const dp = Array.from(new Array(n+1), ()=>new Array(k+1).fill(0))
    dp[0][0] = 1
    for (let i=1;i<=n;++i){
     for (let j=1;j<=n;++j){
             if ( i-j>=0){
                 dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
             }
     }
 }
  return dp[n][k]        
}

编辑于 2021-01-25 19:03:05 回复(0)
Java
从极之渊_头像 从极之渊_ 
public class Solution {

    private static final int MOD = 1_000_000_007;

    private int[][] memo;

    public int divideNumber(int n, int k) {
        this.memo = new int[n + 1][k + 1];
        return dfs(n, k);
    }

    private int dfs(int n, int k) {
        if (n == 0 || n < k) {
            return 0;
        }
        if (k == 1 || k == n) {
            return 1;
        }

        if (memo[n][k] > 0) {
            return memo[n][k];
        }

        return memo[n][k] = (dfs(n - 1, k - 1) + dfs(n - k, k)) % MOD;
    }
}

编辑于 2024-03-13 15:08:12 回复(0)
牛客362459853号头像 牛客362459853号
假设n表示成1 1 1 1 ...111 总共n个1，那么先把前面k个1取出来出来，接下来就是在后面n-k个1插入前面取出来的1（把这k个1当作挡板），总共有n-k+1个空，然后就是公式了。
只是我忘了公式是啥了。
发表于 2021-11-28 19:15:23 回复(0)
C++
Extreme-Ways头像 Extreme-Ways
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int mod=1e9+7;
    int divideNumber(int n, int k) {
        // write code here
        vector<vector<int> >dp(n+1,vector<int>(k+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i&&j<=k;j++){
                dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
                dp[i][j]%=mod;
            }
        return dp[n][k];
    }
};
发表于 2021-09-25 21:58:53 回复(0)
害群之马头像 害群之马 
class Solution {
public:
    int divideNumber(int n, int k) {
        // write code here
        int dp[7][201];  //  k,  n
        for(int k=1;k<=6;k++){
            for(int n=0;n<k;n++ ){
                dp[k][n]=0;
            }
            dp[k][k]=1;
        }
        for(int n=1;n<=200;n++) dp[1][n]=1;
        
        for(int k=2;k<=6;k++){
            for(int n=k+1;n<=200;n++){
                dp[k][n]=dp[k-1][n-1]+dp[k][n-k];
                // 分为两种情况：
                // 1.包含 1（即其中一份只分了1） 等价于 dp[k-1][n-1]
                // 2.都为 大于等于2.   等价于 dp[k][n-k]
                
            }
        }
        return dp[k][n];
    }
};

发表于 2021-06-07 22:58:37 回复(0)
Java
半个西瓜半个夏头像 半个西瓜半个夏 
 /**
     * dp[i][j]将数i分为j分的分法
     * 拆分的结果不包含1的情况：如果不包含1，我们把n拆分成k块时可以看做先将每一块加上个1，
     * 则n还剩余n-k，即f(n-k,k)
     * 拆分的结果包含1的情况：那么就直接选一个1，即f(n-1,k-1)。
     * dp[i][j]=dp[i-j][j]+dp[i-1][j-1]
     * @param n
     * @param k
     * @return
     */
    public int divideNumber (int n, int k) {
        // write code here
        int[][] dp = new int[n+1][k+1];
        dp[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=k&&j<=i;j++){
                dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
            }
        }
        return dp[n][k];
    }
发表于 2021-04-28 17:12:44 回复(0)
十四努力进大厂头像 十四努力进大厂 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    public int divideNumber (int n, int k) {
        // write code here
        int[][]dp=new int[n+1][k+1];
        dp[0][0] = 1;
        for(int i =0;i <=n; i++){
            for(int j =1; j<=i && j <= k;j++){
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            }
        }
        return dp[n][k];
    }
}

发表于 2021-03-05 10:02:30 回复(0)
提交观点

问题信息

动态规划
上传者：牛客301499号
难度：
10条回答 3741浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数的划分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号