題目連結：點選打開連結
放蘋果
| Time Limit: 1000MS | Memory Limit: 10000K |
| Total Submissions: 33112 | Accepted: 20555 |
Description
把M個同樣的蘋果放在N個同樣的盤子裡，允許有的盤子空着不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。
Input
第一行是測試資料的數目t（0 <= t <= 20）。以下每行均包含二個整數M和N，以空格分開。1<=M，N<=10。
Output
對輸入的每組資料M和N，用一行輸出相應的K。
Sample Input
1
7 3 Sample Output
8
思路：
設f(m,n) 為m個蘋果，n個盤子的放法數目，則先對n作讨論，
當n>m：必定有n-m個盤子永遠空着，去掉它們對擺放蘋果方法數目不産生影響。即if(n>m) f(m,n) = f(m,m)
當n<=m：不同的放法可以分成兩類：
1、有至少一個盤子空着，即相當于f(m,n) = f(m,n-1);
2、所有盤子都有蘋果，相當于可以從每個盤子中拿掉一個蘋果，不影響不同放法的數目，即f(m,n) = f(m-n,n).
而總的放蘋果的放法數目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
遞歸出口條件說明：
當n=1時，所有蘋果都必須放在一個盤子裡，是以傳回１；
當沒有蘋果可放時，定義為１種放法；
遞歸的兩條路，第一條n會逐漸減少，終會到達出口n==1;
第二條m會逐漸減少，因為n>m時，我們會return f(m,m) 是以終會到達出口m==0．
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int solve(int m,int n)
{
if(n==1||m==0)
return 1;
if(m<n)
return solve(m,m);
else
return solve(m,n-1)+solve(m-n,n);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",solve(m,n));
}
return 0;
}