本文目录 ⌄
把M个弹珠放到N个盘子里面（我们允许有的盘子为空），你能求出有多少种分法吗？（请注意，例如有三个盘子，我们将5,1,1和1,1,5，视为同一种分法）
输入格式:
输入包含多组测试样例。每组输入的第一行是一个整数t。 接下来t行，每行输入两个整数M和N，代表有M个弹珠和N个盘子。（0=<M<=20; 0<N<=20）
输出格式:
对于每对输入的M和N，输出有多少种方法。
输入样例:
在这里给出一组输入。例如：
1
7 3
输出样例:
在这里给出相应的输出。例如：
8题解
/*
1.动态规划，
2.当前盘子数大于弹珠数时，放法等于盘子数和弹珠数相同的时候
3.当盘子数小于等于弹珠数目时，等于空一个盘子放的数目情形+减去所有盘子放盘子数个弹珠的情形
*/
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> dp(21, vector<int>(21, -1));
int work(int m, int n) { // m 为弹珠数，n为盘子数
if (dp[m][n] != -1) {
return dp[m][n];
}
if (m == 0 || n == 1) {
dp[m][n] = 1;
return 1;
}
if (m < n) {
dp[m][n] = work(m,m);
} else {
dp[m][n] = work(m, n - 1) + work(m - n, n);
}
return dp[m][n];
}
int main() {
int m, n, index;
cin >> index;
vector<int> ans(index);
for (int i = 0; i < index; i++) {
cin >> m >> n;
ans[i] = work(m, n);
}
for (int i = 0; i < index; i++) {
cout << ans[i] << endl;
}
system("pause");
}