数据结构与算法学习笔记----计数类DP

数据结构与算法学习笔记----计数类DP

@@ author: 明月清了个风
@@ first publish time: 2025.2.16

ps⭐️计数类DP主要解决计数问题，这里给出了一题经典模型，提供了两种解题思路，并且给出了代码的优化过程——一种将这题看成完全背包问题，另一种从题目本身出发。

Acwing 900. 整数划分

[原题链接](900. 整数划分 - AcWing题库)

一个正整数$n$可以表示成若干个正整数之和，形如：$n=n_1+n_2+\cdots +n_k$，其中$n_1\ge n_2\ge \cdots \ge n_k,k\ge 1$。

我们将这样的一种表示成为正整数$n$的一种划分。

现在给定一个正整数$n$，请你求出$n$共有多少种不同的划分方法。

输入格式

共一行，包含一个整数$n$。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对$10^9+7$取模。

数据范围

$1\le n\le 1000$

第一种思路

要求将整数$n$分为若干个整数，也就是使用若干个整数凑出整数$n$，并且对于整数没有其他要求，因此可以看成是完全背包问题，也就是有一个容积为$n$的背包，要求使用正整数将其填满，并且每个正整数是无限个，唯一的区别是这里我们要正好凑出容积$n$并且要求的属性也从最大值变成了方案数。

对于状态表示，使用f[i][j]，表示的是从$1\sim i$中的正整数选，总体积恰好为$j$的方案，要求是这个集合中的方案数量

对于状态转移，同样根据最后一个数的选择个数——第$i$个物品选择$0,1,2,\cdots ,k$个进行划分，和完全背包问题完全一致，比如选择$2$个第$i$个物品，那么这一项就是f[i - 1][j - 2 * i]。

那么这样的时间复杂度就是二维状态n^2乘上状态转移计算量$\ln n$(这里是一个调和级数，可以看成是$\log n$)。

当然也可以像完全背包问题那样进行优化:

首先看f[i][j]由哪些状态计算得出：
$$f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2\ast i]+\cdots +f[i-1][j-k\ast i]$$
然后来看另一项f[i][j - i]如何转移
$$f[i][j]=f[i-1][j-i]+f[i-1][j-2\ast i]+\cdots +f[i-1][j-k\ast i]$$
可以发现就是f[i][j]的转移方程除了第一项之外的后面部分，因此就可以得到新的状态转移方程
$$f[i][j]=f[i-1][j]+f[i][j-i]$$
这样就可以将代码中的第三重循环优化掉了。

进一步的，还可以使用一维数组优化， 降低空间复杂度，具体的看代码吧，然后可以复习一下背包问题。

还有一点注意的就是初始化，每次都会提到，这里f[0](也就是二维的f[0~i][0])应该初始化为$1$，因为从前$0\sim i$个数中选出体积为$0$的方案就只有一种——什么都不选。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#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;
    
}

第二种思路

这里可以使用另一种状态表示方法，使用f[i][j]，表示的是总和是$i$，并且恰好由$j$个数表示。

这里的状态划分比较难，可以背下来，划分为两类，分别是表示方法中最小值是$1$和最小值不是$1$。

其中，最小值是$1$的表示方法，可以由f[i - 1][j - 1]转移而来，也就是总和中减去了这个$1$，并且表示方法中整数个数也减去$1$个数。

另一类比较抽象，因为最小值大于$1$，无法像第一类一样直接转移，这里我们可以将集合中的$j$个数每个数都减去$1$，那么总和会减去$j$，状态表示为f[i - j][j]，可以通过将这个状态中的$j$个数都加上$1$变回去，因此两种状态是等价的，可以这样转移

所以最终的状态转移方程就是$f[i][j]=f[i-1][j-1]+f[i-j][j]$，但是这里最后的答案需要遍历一遍，也就是$f[n][1]+f[n][2]+\cdots +f[n][n]$。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#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;
    
}