题解 | #放苹果#

// mark一下

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 状态转移方程
    // 1. m < n  则: dp[i][j] = dp[i][i];
    // 2. m >= n 则：dp[i][j] = dp[i][j - 1] + dp[i - j][j]
    // 终止条件
    // m = 0 || m = 1，即: dp[0][j] = 1; dp[1][j] = 1;
    // n = 1，即: dp[i][1] = 1
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int m = in.nextInt();
            int n = in.nextInt();
            System.out.println(func(m, n));
        }
    }

    public static int func(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int k = 0; k <= n; k++) {
            dp[0][k] = 1;
            dp[1][k] = 1;
        }
        for (int k = 0; k <= m; k++) {
            dp[k][1] = 1;
        }
	  // todo ： 为啥i和j一定得从2开始，从1结果不对呢？
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                if (i < j) {
                    dp[i][j] = dp[i][i];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }
        return dp[m][n];
    }
}