题解 | #放苹果#

import java.util.Scanner;

/**
 * 【放苹果】
 *
 * 描述：把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int appleNum = sc.nextInt();
        int plateNum = sc.nextInt();

        int[][] dp = new int[appleNum + 1][plateNum + 1];

        for (int i = 0; i < plateNum + 1; i++) {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }

        for (int i = 1; i < appleNum + 1; i++) {
            dp[i][0] = 1;
            dp[i][1] = 1;
        }

        for (int i = 2; i < appleNum + 1; i++) {
            for (int j = 2; j < plateNum + 1; j++) {
                if (i < j) {
                    dp[i][j] = dp[i][i];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }

        System.out.println(dp[appleNum][plateNum]);
    }
}