题解 | 数的划分

class Solution {
  public:
    /**
     令dp[i][j]表示把数字i分成j份的方案数。
    i<j, 无解. 因为每一份至少是1.
    i==j, 1种方案。
    i>j. 先把每一份都分配上1，剩下的i-j可以分成0份dp[i-j][0]，1份dp[i-j][1]，2份dp[i-j][2],3份dp[i-j][3],。。。。。。j份，故有如下公式：
    dp[i][j] = 上面的k=1至j份种情况的求和；
    用d[i][j] - dp[i-1][j-1] = 和的差 = dp[i-j][j]
    得dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
    实现之, 最后即为答案。
     */
    const int M = 1e9 + 7;

    int divideNumber(int n, int k) {
        if (n < k) {
            return 0;
        }

        vector< vector<int>> dp(n + 1, vector<int>(k + 1, 0));

        //k=1，dp[i][1]=1;
        for (int i = 0; i <= n; i++) {
            dp[i][1] = 1; //分成一份只能一种情况
        }

        for (int i = 0; i <= min(n, k); i++) {
            dp[i][i] = 1;
        }
        dp[0][0] = 0;

        for (int j = 1; j <= k; j++) {
            for (int i = j; i <= n; i++) { //i的数应该》=份数
                dp[i][j] = ( dp[i - 1][j - 1] + dp[i - j][j]) % M;
            }
        }

        return dp[n][k];
    }
};