分苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？M, N为自然数。说明：如有7个苹果，2个盘子，则(5, 1, 1)和(1, 5, 1)和(1, 1, 5)都是同一种分法。

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);
	}
}