题解 | #放苹果#

import java.util.Scanner;

/**
 * 比较直接的解法，由于5,1,1和1,5,1为同一种，那么我们对于每一种放法，
 * 我们可以让前一个盘子放的苹果数不少于后面的苹果数，保证放法唯一。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt(), m = sc.nextInt();
            System.out.println(dfs(m, n, n));
        }
    }

    /**
     * @param m   盘子数
     * @param n   苹果数
     * @param pre 前一个盘子放的苹果数
     * @return
     */
    private static int dfs(int m, int n, int pre) {
        // 苹果数为0，不需要再放
        if (n == 0) {
            return 1;
        }

        // 没有盘子了，返回0
        if (m == 0) {
            return 0;
        }

        int res = 0;
        // 当前盘子苹果数不能多于前一个盘子的苹果数
        for (int i = pre; i > 0; i--) {
            res += dfs(m - 1, n - i, i);
        }

        return res;
    }
}