题解 | #放苹果#
放苹果
https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
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); } } }