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