C++ 解法, 执行用时: 25ms, 内存消耗: 19972KB, 提交时间: 2022-06-08

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

C++ 解法, 执行用时: 31ms, 内存消耗: 20096KB, 提交时间: 2022-06-04

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

C++ 解法, 执行用时: 32ms, 内存消耗: 20128KB, 提交时间: 2022-05-08

class Solution {
  public:
    static const int M = 1e9 + 7;
    int divideNumber(int n, int k) {
        vector<vector<int> > z(n + 1, vector<int>(k + 1, 0));
        for (int i = 0; i <= k; i++) {
            z[i][i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(k, i); j++) {
                z[i][j] = (z[i - 1][j - 1] + z[i - j][j]) % M;
            }
        }
        return z[n][k];
    }
};

C++ 解法, 执行用时: 32ms, 内存消耗: 20140KB, 提交时间: 2022-06-14

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int divideNumber(int n, int k) {
        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 <= k; ++j) {
                if (i >= j) {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % 1000000007;
                }
            }
        }
        return dp[n][k];
    }
};

C++ 解法, 执行用时: 33ms, 内存消耗: 20092KB, 提交时间: 2022-05-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    static const int M = 1e9 + 7;
    int divideNumber(int n, int k) {
        // write code here
        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]) % M;
            }
        }
        return dp[n][k];
    }
};