分弹珠

把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");
}