public class SplitNumber {
    public static void main(String[] args) {
        int pre = 1;
        int rest = 27;
        System.out.println(process(1,rest));
        System.out.println(dp(1,rest));
    }


    // pre 上一个拆出来的数
    // rest 剩下拆的数
    public static int process(int pre, int rest){
        if(rest == 0){
            return 1;
        }

        if(pre > rest){
            return 0;
        }

        int way = 0;
        for (int i = pre; i <= rest; i++) {
            way += process(i, rest-i);
        }

        return way;
    }

    public static int dp(int pre, int rest){
        int N = rest + 1;
        int[][] dp = new int[N][N];
        // 行表示rest  列表示pre
        for (int i = 1; i < dp.length; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < dp.length; i++) { // i:rest
            for (int j = 1; j <= i; j++) {// j:pre
                for (int k = j; k <=i; k++) {
                    dp[i][j] += dp[i-k][k];
                }

            }
        }

        return dp[N-1][1];
    }
}