一本通-1192：放苹果（计数DP-划分数）

【题目描述】 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

【输入】 第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。

【输出】 对输入的每组数据M和N，用一行输出相应的K。

【输入样例】 1 7 3

【输出样例】 8

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int m, n;
vector<vector<long long> > d(15, vector<long long>(15));

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;

    d[0][0] = 1;

    for (int i = 1; i <= 12; ++i) {
        for (int j = 0; j <= 12; ++j) {
            d[i][j] = (j >= i ? d[i][j - i] : 0) + d[i - 1][j];
        }
    }

    while (caseNum--) {
        cin >> m >> n;
        cout << d[n][m] << endl;
    }

    return 0;
}

划分数的模板，和POJ 1664 放苹果基本上是一个题型。状态转移方程写好后，还有一个关键点就是初始化条件，尤其需要注意的就是多重集和组合数和划分数的初始条件的不同。