题解 | #数的划分#

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
        long A[][] = new long[n+1][k+1];
        int tmp = 0;
        for(int i = 1;i<=n;i++){
            
            A[i][1] = 1;
        }
         for(int i = 1;i<=k;i++){
            
            A[i][i] = 1;
        }
        for(int i=3;i<=n;i++){
            for(int j=2;j<i&&j<=k;j++){
                A[i][j] = (A[i-1][j-1]);//当最小数为1时，把i分成j份就变成了把i-1分成j-1份，1就是单独一份；
                tmp = i;
                while(tmp-j-1>0){//当最小数为2时，先把j个坑位预先减1把问题化成与前述一致，剩下就变成了i-j-1份分成j-1份；
                    A[i][j] += (A[tmp-j-1][j-1]);
                    tmp -= j;
                }
                A[i][j] = A[i][j]%(1000000007);
            }
        }
        
        return (int)A[n][k]%(1000000007);
        
    }
}