POJ-1664 放苹果（划分数模板题）

Description

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

Input

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

Output

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

Sample Input

1
7 3

Sample Output

8

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int n = 1005, m = 1005;
vector<vector<int>> d(n, vector<int>(n));

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

    d[0][0] = 1;
    for (int i = 1; i <= 10; ++i) {
        for (int j = 0; j <= 10; ++j) {
            if (j >= i) 
                d[i][j] = d[i][j - i] + d[i - 1][j];
            else
                d[i][j] = d[i - 1][j];
        }
    }
    int caseNum;
    cin >> caseNum;
    while (caseNum--) {
        int m, n;
        cin >> m >> n;
        cout << d[n][m] << endl;
    }

    return 0;
}

用$d[i][j]$表示把$j$划分成不超过$i$组的结果，那么最终我们需要的结果是$d[m][n]$，然后去寻找状态转移方程。考虑$n$的$m$划分$a_i(\sum_{i=1}^m a_i = n)$，如果对于每一项$\{a_i - 1\}$都大于0，那么相当于$n-m$的$m$划分，如果至少有一项$a_i$为0，那么相当于$n$的$m-1$划分。所以得到状态转移方程： $$ d[i][j] = d[i][j-i] + d[i -1 ][j] $$

这道题的初始化部分还是很重要的，及时复习。

这道题还可以用**母函数**去做。