计数DP

计数类DP

整数划分

可看作是完全背包问题的改版，将1~n的数看作体积，每个物品使用无限次，恰好能装满背包体积n的总方案数。

注意初始化时，我们要求的与完全背包不同，完全背包要求最大的价值，该题要求最大的方案数，因此我们至少有一种方案，应该全部初始化为1。

状态表示：f[i] [j]表示使用前i个整数恰好拼成j的方案数。

因此有

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;

由完全背包的公式推得：

f[i][j] = max(f[i][j], f[i - 1][j] + f[i][j - i]);

再加上一维优化：

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int n;
    cin >> n;
    q[0] = 1; // 初始化状态为1

    for (int i = 1; i <= n; i ++ ){
        for (int j = i; j <= n; j ++ ){
            q[j] = (q[j] + q[j - i]) % mod;
        }
    }

    cout << q[n] << endl;
}