非常哈人动态规划，使我脑子旋转。

概念

计数 DP 是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题。

例题

整数划分

900. 整数划分 - AcWing 题库

背包问题思路

可将问题转换为一个完全背包问题。背包容量为 n，有 n 个物品，第 i 个物品的容量为 i，价值为 1。然后求物品刚好放满背包的方案数。

const int MOD = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    
    // 完全背包问题求方案数
    vector<int> dp(n + 5, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            dp[j] = (dp[j] + dp[j - i]) % MOD;
    
    cout << dp[n];
}

其他 DP 解法

状态分析：f[i, j] 的意思是，所有总和是 i，并且恰好是 j 个数的和的方案。我们要求方案的数量。

状态计算：接下来想想，如何通过一步操作得到 f[i, j]：

• 方案中最小值是 1，那么 f[i - 1, j - 1] 再加个 1 就能得到 f[i, j]；
• 方案中最小值＞1，那么 f[i - j, j] 方案中的每个数都加 1 就能得到 f[i, j]；

因此总方案数 f[i, j] = f[i - 1, j - 1] + f[i - j, j]。

const int MOD = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    
    vector<vector<int>> dp(n + 5, vector<int>(n + 5, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % MOD;
    
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + dp[n][i]) % MOD;
    cout << ans;
}

练习题