APP
描述：
把m個同樣的蘋果放在n個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1?是同一種分法。?
數(shù)據(jù)范圍：0≤m≤10，1≤n≤10?。
?
動態(tài)規(guī)劃 理解：
定義dp[m + 1][n + 1]，可以理解為：將0 - m個蘋果放入1 - n 個盤子的中的方法，每一行，則為將i個蘋果放入1 - n個盤子中的方法數(shù)。
根據(jù)m和n的關(guān)系：
1、蘋果的數(shù)量少于盤子時，即 m < n? --> dp[i][j] = dp[i][i]
2、蘋果的數(shù)量大于等于盤子時，分兩種情況：
1) 沒有空盤子時，則從每個盤子中拿走一個蘋果，擺放的方法數(shù)是一樣的。dp[i][j] = dp[i - j][j]
? ? ? ?2) 有空盤子時，此種情況不太好理解：有一個空盤子時? dp[i][j] = dp[i][j - 1]。其實這里的有一個空盤子，是個遞歸的過程dp[i][j - 1] 包含了dp[i][j - 2]，以此類推：dp[i][j - 1]，包含了 j - 1，... , 1個空盤子的情況
--> 有空盤子時，dp[i][j] = dp[i][j - 1];
--> m >= n 時， dp[i][j] = dp[i - j][j] + dp[i][j - 1]；
?
邊界條件：
1、0個盤子時，當(dāng)然沒法擺了，只能是0： dp[i][0] = 0;
2、一個盤子時，所有的蘋果只能放到這一個盤子中：dp[i][1] = 1
3、0個蘋果時，所有盤子都是空的：dp[0][j] = 1;
?
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
while (cin >> m >> n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // m個蘋果，放到n個盤子中
// 0個盤子和一個盤子時，只有一種方法
for (int i = 0; i <= m; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
// 0個蘋果時
for (int i = 0; i <= n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i < j) {
dp[i][j] = dp[i][i];
} else {
dp[i][j] = dp[i - j][j] + dp[i][j - 1];
}
}
}
cout << dp[m][n] << endl;
}
return 0;
}
本文摘自 ：https://www.cnblogs.com/
