题解 | #数的划分#

设f(i,j)为i分成j份的方案数
初值：
当j=1以及i=j时f(i,j)=1
递推：
两种情况

1.j份中至少一个是1，方案数为f(i-1,j-1)
2.j份中一份1都没有，考虑将i-j分为j份，再往j份中的每一份+1，方案数为f(i-j,j）

故有递推式：
f ( i , j ) = f ( i − 1 , j − 1 ) + f ( i − j , j ) f(i,j)=f(i-1,j-1)+f(i-j,j)
f(i,j)=f(i−1,j−1)+f(i−j,j)

    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++){
                if(i >= j){
                    dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][k];
    }