题解 | #数的划分#

动态规划思想：时间复杂度O(nk)，空间复杂度O(nk)。

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int divideNumber(int n, int k) {
        if(n < k)   return -1;
        if(n == k)  return 1;
        // dp[i][j]表示将整数i划分j份的方案数
        vector<vector<int>> dp(n+1, vector<int>(k+1));
        int mod = 1e9 + 7;
        // 划分1份则只有一种方案
        for(int i=1; i<=n; ++i){
            dp[i][1] = 1;
        }
        // 数i划分i份，每份为1，只此1种方案
        for(int i=0; i<=k; ++i) dp[i][i] = 1;
        // 状态转移
        for(int i=2; i<=n; ++i){
            // j的最大取值为 min(i,k)， 不然可能报错数组越界
            for(int j=2; j<=min(i,k); ++j){
                // 状态转移方程 dp[i][j] = dp[i-j][j] + dp[i-j][j-1] + ... + dp[i-j][1]
                // 代表含义是先给j个位置每个分配1，然后剩余的i-j可以分配给j个位置/j-1/.../1个位置
                // 而 dp[i-1][j-1] = dp[i-j][j-1] + ... + dp[i-j][1]
                // 所以 dp[i][j] = dp[i-j][j] + dp[i-1][j-1]
                dp[i][j] = (dp[i-j][j] + dp[i-1][j-1])%mod;
            }
        }
        return dp[n][k];
    }
};