NC152 数的划分

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/24c2045f2cce40a5bf410a369a001da8?

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

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
        if(k > n)return 0;//如果划分步骤都比值还大是可能有划分结果的
         /*
        k == n的时候 那么就是每个位置都是1
        k == 1的时候，那么就是第一个位置就是本身
        n = k + 1的时候 划分就是 1 1 1 .... n- (k - 1)
        */
        if(k == n || k == 1 || n == k + 1)
            return 1;
        //dp[i][j]表示数字i划分j份的时候方案数有多少种
        vector<vector<int>> dp(n + 1, vector<int>(k + 1,0));
        dp[0][0] = 1;//数字0划分为0份总共有1种分法
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= k;j ++){
                if(j <= i){//划分的份数要<= 给定的数 
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j])%mod;
                }
            }
        }
        return dp[n][k];
    }
};

Java版本：

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
        if(k > n)return 0;//如果划分步骤都比值还大是可能有划分结果的
         /*
        k == n的时候 那么就是每个位置都是1
        k == 1的时候，那么就是第一个位置就是本身
        n = k + 1的时候 划分就是 1 1 1 .... n- (k - 1)
        */
        if(k == n || k == 1 || n == k + 1)
            return 1;
        int mod = 1000000007;
        //dp[i][j]表示数字i划分j份的时候方案数有多少种
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;//数字0划分为0份总共有1种分法
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                if(i >= j){//划分的份数要<= 给定的数
                    dp[i][j] = (dp[i - j][j] + dp[i - 1][j - 1])%mod;
                }
            }
        }
        return dp[n][k];
    }
}

Python版本:

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int 被划分的数
# @param k int 化成k份
# @return int
#
class Solution:
    def divideNumber(self , n , k ):
        # write code here
        if k > n:return 0#如果划分步骤都比值还大是可能有划分结果的
        '''
        k == n的时候 那么就是每个位置都是1
        k == 1的时候，那么就是第一个位置就是本身
        n = k + 1的时候 划分就是 1 1 1 .... n- (k - 1)
        '''
        if k == n or k == 1 or n == k + 1:
            return 1;
        mod = 1000000007
        #dp[i][j]表示数字i划分j份的时候方案数有多少种
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1#数字0划分为0份总共有1种分法
        for i in range(1,n+1):
            for j  in range(1,k+1):
                if i>= j:#划分的份数要<= 给定的数
                    dp[i][j] = (dp[i - j][j] + dp[i - 1][j - 1])%mod
        return dp[n][k];

JavaScript版本:

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int 被划分的数
 * @param k int 化成k份
 * @return int
 */
function divideNumber( n ,  k ) {
    // write code here
        if(k > n)return 0;//如果划分步骤都比值还大是可能有划分结果的
         /*
        k == n的时候 那么就是每个位置都是1
        k == 1的时候，那么就是第一个位置就是本身
        n = k + 1的时候 划分就是 1 1 1 .... n- (k - 1)
        */
        if(k == n || k == 1 || n == k + 1)
            return 1;
        let mod = 1000000007;
        //dp[i][j]表示数字i划分j份的时候方案数有多少种
        let dp = Array.from(new Array(n+1), ()=>new Array(k+1).fill(0))
        dp[0][0] = 1;//数字0划分为0份总共有1种分法
        for(let i = 1; i <= n; i++){
            for(let j = 1; j <= k; j++){
                if(i >= j){//划分的份数要<= 给定的数
                    dp[i][j] = (dp[i - j][j] + dp[i - 1][j - 1])%mod;
                }
            }
        }
        return dp[n][k];
}
module.exports = {
    divideNumber : divideNumber
};