HJ61 放苹果

题目：

HJ61 放苹果

题解：递归

f(m,n)表示将m个苹果放在n个盘子中所有的放法。

1. 当n > m时，一定有盘子空着，等效于将m个苹果放到m个盘子中，即f(m,n) = f(m,m)
2. 当 n < m时，
   1. 没有空盘子，那么每个盘子至少有一个，那么放与不放没有区别，把每个盘子中的苹果都先去掉，即f(m,n) = f(m-n,n)
   2. 至少有一个空盘，那么等效于将m个苹果放到n-1个盘子中，即即f(m,n) = f(m,n-1)
3. 递归边界，m = 0 表示没有苹果，只有一种分法就是都不放；n = 1 只有一个苹果，放哪都一样也是只有一种分法。

    public int getApple(int m, int n) {
        if (m == 0 || n == 1) {
            return 1;
        }

        if (n > m) {
            return getApple(m, m);
        }

        return getApple(m-n, n) + getApple(m, n-1);
    }

时间复杂度：O()