题解 | #放苹果#递归and动态规划（数组）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int apple = in.nextInt();
        int dish = in.nextInt();

        // 递归
        // System.out.println(resolve(apple, dish));

        // 数组
        int d[][] = new int[apple+1][dish+1];
        for (int i = 0; i < apple+1; i++) {
            d[i][0] = 1;
            d[i][1] = 1;
        }
        for (int i = 0; i < dish+1; i++) {
            d[0][i] = 1;
            d[1][i] = 1;
        }

        for (int i = 2 ; i < apple + 1 ; i++) {
            for (int j = 2; j < dish + 1 ; j++) {
                if (i < j) {
                    d[i][j] = d[i][i];
                    continue;
                }
                d[i][j] = d[i][j - 1] + d[i - j][j];
            }
        }

        System.out.println(d[apple][dish]);
    }

    static int resolve(int apple, int dish) {
        if (apple == 0 || dish == 0 || apple == 1 || dish == 1) {
            return 1;
        }

        if (apple < dish) {
            return resolve(apple, apple);
        }
        // 如何分解问题是关键
        return resolve(apple, dish - 1) + resolve(apple - dish, dish);
    }
}