題目出處
----------------------------------------------------------------------------題目----------------------------------------------------------------------------
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
----------------------------------------------------------------------------題目結束-----------------------------------------------------------------------
解法：遞歸
思路（結合遞歸詳述）：
遞歸的作用在於把問題的規模不斷縮少，直到問題縮少到能簡單地解決
問：那麼在這個問題上，如何減少問題規模呢？
答：這個問題有 m 個蘋果和 n 個盤子，明顯地，分別減少 m 和 n 的個數。就能達到把整個問題規模減少。而 m 的減少需要以盤子的個數為最少單位進行縮少。
新問題與原問題有著相同的形式 www.2cto.com
當縮少規模後，產生的新問題與原問題的意思是一樣。也即新問題具有相同的形式：同樣是求 m 個蘋果放到 n 個盤子上的放法
遞歸的結束需要簡單情景
問：這個問題的簡單情景是什麼？
答：隨著不斷進行向下遞歸，會產生如下的幾種簡單情景：
n = 1，盤子剩下一個，即只有一種放法；
m < 0，即存在空盤子。所以這種情況包含了在 n 不斷減少的情況中；
m = 0，即蘋果已經全放完，沒有多余。所以這屬於一種放法；
遞歸跳躍的信任
我們這裡只需要思考：如何做能讓問題規模減少、如何正確分析出簡單情景即可。我們不需要去過多思考實現細節。
----------------------------------------------------------------------------代碼----------------------------------------------------------------------------
[cpp]
#include <iostream>
using namespace std;
int fun(int m, int n)
{
//當蘋果已全部放滿時
if (m == 0) return 1;
//當盤子剩下一個時
if (n == 1) return 1;
//當m<0時候的放法包含在fun(m,n-1)中
if (m < 0) return 0;
return fun(m-n, n) + fun(m, n-1);
}
int main()
{
int t;
int m, n;
cin >> t;
while (t--)
{
cin >> m >> n;
cout << fun(m, n) << endl;
}
return 0;
}
