# 題目描述 放蘋果問題：把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？ （注：5,1,1和1,1,5是同一種分法） 解題分析： 設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時，所有蘋果都必須放在一個盤子里，所以返回１； 當m==0(沒有蘋果可放)時，定義為１種放法； # 遞歸 ~~~ int fun(int m,int n) //m個蘋果放在n個盤子中共有幾種方法 { if(m==0||n==1) //因為我們總是讓m>=n來求解的，所以m-n>=0,所以讓m=0時候結束，如果改為m=1， return 1; //則可能出現m-n=0的情況從而不能得到正確解 if(n>m) return fun(m,m); else return fun(m,n-1)+fun(m-n,n); } ~~~ # 動態規劃 ~~~ //放蘋果 int main() { int apple, plate; cin >> apple >> plate; if (apple < 0 || apple > 10 || plate < 1 || plate > 10) { cout << -1 << endl; return -1; } vector<vector<int> > ivec(11, vector<int>(11, 0)); for (int i = 0; i < 11; i++) { ivec[0][i] = 1; ivec[i][1] = 1; } for (int i = 1; i <= 10; ++i) { for (int j = 1; j <= 10; ++j) { if (j <= i) ivec[i][j] = ivec[i][j - 1] + ivec[i - j][j]; else ivec[i][j] = ivec[i][i]; } } cout << ivec[apple][plate] << endl; return 0; } ~~~