题解 | #放苹果#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        if (m == 0 || m == 1 || n == 1) {
            System.out.println(1);
            return;
        }
        helper(m, n);
    }
    
    public static void helper(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }
        
        for (int apple = 2; apple <= m; apple++) {
            for (int plate = 2; plate <= n; plate++) {
                if (apple < plate) {
                    // 苹果少于盘子，必然会有空盘子
                    // 空盘子等价，则等同于apple个苹果放到apple个盘子里
                    dp[apple][plate] = dp[apple][apple];
                } else {
                    // 苹果多余盘子数，依据是否有空盘子有两种情况
                    // 1.多余的apple-plate个苹果放到plate的情景
                    // 2.apple个苹果放到plate-1个盘子的情况（至少一个盘子为空）
                    dp[apple][plate] = dp[apple-plate][plate] + dp[apple][plate-1];
                }
            }
        }
        
        System.out.println(dp[m][n]);
    }
}