900. 整数划分

将正整数 \(n\) 表示成一系列正整数之和，\(n=n_1+n_2+…+n_k\)，其中 \(n_1 \geq n_2 \geq …\geq n_k \geq 1,\ k \geq 1\)。正整数 \(n\) 的这种表示称为正整数 \(n\) 的划分。正整数 \(n\) 的不同的划分个数正整数\(n\)的划分数。

解法一

思路：有 种物品，物品的体积分别为 ，每种物品可以用无限次，求恰好装满容量为 的背包的方案数。于是，该题就转化为求完全背包的方案数。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;

    return 0;
}

解法二

状态： 表示和为 ，个数为 的方案的个数。

在这种状态表示下，状态转移就比较难想了。

1. 的所有方案中最小值是 ：
2. 的所有方案中最小值大于 ：

故状态转移方程：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> n;

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}

900. 整数划分

原文：https://www.cnblogs.com/fxh0707/p/14643058.html