POJ1664 放苹果（递归）

题意：

中文题，把m个苹果放入n个相同的盘子，盘子中可以不放苹果，问有几种方法

要点：

一开始我还以为是数学题，这不是组合概率问题吗？后来看网上的解释原来是递归：

用f(m)(n) 记录有几种方法：

1.m=1||n=1时都只有一种，f(m)(n)=1

2.m<n时，就相当于m个苹果放m个盘子，f(m)(n)=f(m)(m)

3.m=n时，有两种方式，第一种是每个盘子都放，只有全为1一种可能，第二种是至少一个盘子是空的，f(m)(n)=1+f(m)(n-1)，我们只要算n-1的情况就好，因为n-1的情况本身包括放n-1和放n-2两种情况，这样一层层递归下去

4.m>n时，也分为两种情况：全放和至少一个没放，全放相当与先所有的盘子先放一个，再分配剩下的m-n个苹果，f(m)(n)=f(m-n)(n)+f(m)(n-1)

#include<stdio.h>
int f[15][15];int put_apple(int m, int n)//有动态规划思想
{if (m == 1 || n == 1)f[m][n] = 1;else if (m < n)f[m][n] = put_apple(m, m);else if (m == n)f[m][n] = 1 + put_apple(m, n - 1);else if (m > n)f[m][n] = put_apple(m - n, n) + put_apple(m, n - 1);return f[m][n];
}
int main()
{int t;scanf("%d", &t);while (t--){int m, n;scanf("%d%d", &m, &n);printf("%d\n", put_apple(m, n));}return 0;
}