小明准备把M个同样的苹果分在N个同样的篮子里，允许有的篮子空着不放，那么一共有多少种不同的分法呢？

说明：5，1，1和1，5，1 是同一种分法。

输入: 每个用例包含二个整数M和N。0<=M<=10，1<=N<=10。 输出: 一个整数K，表示一共有K种分苹果的方法。 样例输入: 7 3 样例输出: 8 样例输入: 8 3 样例输出: 10

参考解答

思路：

主要的思路是“降维+递归”，假设m为苹果数、n为篮子数。以 f(8,3) 为例，它可以被分解为 f(8,3)=f(8,2)+f(5,2)+f(2,2)，分析如下：

1. 固定篮子c的苹果为0，相当于8个苹果在a b篮子中组合，即f(8,2)：

   8 0 0 + 0 0 0
   7 1 0 + 0 0 0
   6 2 0 + 0 0 0
   5 3 0 + 0 0 0
   4 4 0 + 0 0 0
   

2. 三个篮子中都统一放入一个苹果，这时固定篮子c的苹果为0，相当于剩下的5个苹果在a b篮子中组合，即f(5,2)：

   5 0 0 + 1 1 1
   4 1 0 + 1 1 1
   3 2 0 + 1 1 1
   

3. 三个篮子中都统一放入两个苹果，这时固定篮子c的苹果为0，相当于剩下的2个苹果在a b篮子中组合，即f(2,2)：

   2 0 0 + 2 2 2
   1 1 0 + 2 2 2
   

4. 三个篮子中不可能都放入三个苹果，不够分，到此为止，这一轮递归结束。
5. 继续进行下几轮递归，f(5,2)=f(5,1)+f(3,1)+f(1,1)，f(2,2)=f(2,1)+f(0,1)
6. 思考一下当n=1（篮子数）时，不管m=? 只能有一种放法。即f(m,1)=1

java实现：

public static void main(String[] args) {
  System.out.println(f(8,3));
}

public static int f(int m, int n) {
  if(n == 1) {
    return 1;
  }
  int sum = 0;
  // 比如m=8,n=3, 则累加 f(8,2)+f(8-3,2)+f(8-3-3,2)
  for(int i = m; i >=0; i-=n) {
    sum += f(i, n-1);
  }
  return sum;
}