题目描述
代码语言：javascript复制把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？M, N为自然数。说明：如有7个苹果，2个盘子，则(5, 1, 1)和(1, 5, 1)和(1, 1, 5)都是同一种分法。思路分析
思路一： 我们令f(M)(N)表示M个苹果正好使用N个盘子时的分法个数(当M<N时f(M)(N) = 0)。 假设没有空盘子，则如果M>N，题目可以转换为f(M)(N) = f(M-N)(N) 假设有空盘子，则可以按照空盘子的个数来递归求解，即只有一个空盘子的情况解为:f(M)(N-1), 只有两个空盘子时解为：f(M)(N-2) .... 有N-1个空盘子时，解为f(M)(1)
思路二： 我们令f(M)(N)表示将M个苹果放入N个盘子的解法。则同样分有空盘子和无空盘子的情况： 假设没有空盘子，则f(M)(N) ===> f(M-N)(N)，即首先N个盘子每个盘子放一个苹果，然后将题目转换成M-N个苹果放入N个盘子（缩小M） 假设有一个空盘子，则题目可以转换成f(M)(N) ===> f(M)(N-1) （缩小N）。 此时f(M)(N)表示的是将M个苹果放入N个盘子的最终解，通过上面的分析的到，他应该是上面两个子问题解的和： 即 f(M)(N) = f(M-N)(N) f(M)(N-1)
最终得到代码如下：
DivideApple
代码语言：javascript复制public class DivideApple {
public static void main(String[] args) {
DivideApple divideApple = new DivideApple();
int m = 8;
int n = 3;
System.out.println(divideApple.divideAppleTwo(m, n));
}
/**
* 该方程表示m个苹果放入n个盘子的最终解的个数
* @param m 苹果个数
* @param n 盘子个数
* @return 最终解的个数
*/
public int divideAppleTwo(int m, int n) {
if (m == 0 || n == 1) {
return 1;
}
if (m < n) {
return divideAppleTwo(m, m); // 如果苹果个数小于盘子个数，则一定会有至少n-m个空盘子，将问题化为m个苹果放入m个盘子的解的个数
}
return divideAppleTwo(m - n, n) divideAppleTwo(m, n - 1);
}
}
