题解 | #放苹果#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //        把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
//        注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
        //这道题是一个分组问题，分情况讨论，把m分为n个数，可以有0
        //递归思路，m个苹果，n个盘子，如果m>=n,分两种情况：
        //①：至少有一个盘子没有苹果，那相当于m个苹果分给n-1个盘子
        //②：①的反面是每个盘子都有苹果，那相当于m-n个苹果分给n个盘子
        //如果m<n,盘子多，那就相当于把m个苹果放入m个盘子
        //这样递归下去，传入方法的参数会越来越小，直到盘子变为1个或者苹果变为1个
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(group(m, n));
        scanner.close();
    }
    public static int group(int m, int n) {
        if (m <= 1 || n <= 1) {
            return 1;
        } else if (m < n) {
            return group(m, m);
        } else {
            return group(m, n - 1) + group(m - n, n);
        }
    }

}