题解 | #放苹果#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int[] dp = new int[in.nextInt() + 1];
            Arrays.fill(dp, 1);
            int plat = in.nextInt();
            for (int i = 2; i <= plat; i++) for (int j = 0; j < dp.length; j++) if (j - i >= 0) dp[j] += dp[j - i];
            System.out.println(dp[dp.length - 1]);
        }
    }
}

动态规划：

最后一个盘子有两种可能

一种是有空盘，假设最后一个盘子就是空盘之一，所以直接等于少一个盘子的结果

另一种是没有空盘，先往所有盘子放苹果，然后就等于苹果数减少盘子数的结果

因此推出状态转移公式：dp[j] += dp[j - i];