算法：计数类dp-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法：计数类dp。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

计数类动态规划（Counting DP）是一种用来解决计数问题的动态规划技术，它通常用于求解在给定条件下满足某种性质的组合或序列的总数。 计数类DP问题的特点是要求计算所有可能情况的数量，而不是求最值或是否存在这样的情况。 当然我们在使用计数类dp的时候，没必要去和线性dp区分开来，会用就行。
我们先举个栗子，来说明计数类dp是个啥，然后再来说明思路。

一、举个栗子

例子1：爬楼梯问题

假设你在爬楼梯，每次你可以爬1个或2个台阶。给定楼梯的总台阶数n，你有多少种不同的方法可以爬到楼顶？

分析：让我们用dp[i]表示到达第i阶楼梯的方法数量。如果我们考虑最后一步，我们可以从第i-1阶跨一步到达第i阶，或者从第i-2阶跨两步到达第i阶。因此，到达第i阶的方法数是到达第i-1阶和第i-2阶方法数的和。

状态转移方程：dp[i] = dp[i-1] + dp[i-2]

初始化：dp[1] = 1, dp[2] = 2

例子2：不同路径

一个机器人位于一个m x n网格的左上角，机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

分析：定义dp[i][j]为到达网格中(i, j)位置的路径数量。要到达(i, j)，机器人只能从(i-1, j)向下走，或从(i, j-1)向右走，所以dp[i][j]是这两个来源的路径数之和。

状态转移方程： dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化：网格的最上方dp[0][j] = 1和最左方dp[i][0] = 1，因为只有一种方式到达。

例子3：计数子序列

给定一个字符串，计算不同的子序列个数。子序列是从给定序列中删除一些字符（也可以不删除）后形成的新序列。

分析：这个问题稍微复杂一点。我们可以使用dp[i]表示考虑到字符串的第i个字符时的不同子序列个数。对于每个新字符，它可以选择加入之前的子序列中，或者不加入。

状态转移：如果当前字符之前没出现过，dp[i] = 2 * dp[i-1]。如果当前字符之前出现过，需要减去上一次该字符出现时的子序列个数，以避免重复计数。

二、基本思路

计数类dp的基本思路不好说，因为本质上就是要找到一个状态以及状态转移，使得满足要求计算所有可能情况的数量并且避免重复计算。 这也是最难得一步。

计数类DP的基本思路涉及以下几个步骤：

定义状态：根据问题的特性，合理定义状态，表示达到当前状态的可能情况数量。状态通常涉及考虑的元素个数、已选择元素的性质（如总和、最大值等）以及其他约束条件。
确定状态转移方程：根据问题的性质，确定从已知状态到未知状态的转移方式。状态转移方程描述了在当前决策下，如何通过之前的状态来计算当前状态的值。
初始化：正确初始化DP数组，特别是基础情况（通常是递归的边界条件），这些基础情况直接决定了递推的起点。
计算顺序：根据状态之间的依赖关系确定计算顺序，确保在计算某个状态之前，它依赖的状态已经被计算。
结果汇总：根据问题要求，从DP数组中提取最终结果。有时可能需要遍历DP数组的某些部分来汇总最终的计数结果。

三、典型例题

一、ACWing：900. 整数划分

900. 整数划分
算法：计数类dp,# 计数类dp,算法,算法
这类问题的难点再于找到状态和状态转移方程，以及看出来它是一个动态规划题。

1、解法一

用题目本身最接的方式去思考：
对于数n和数 n+1的划分方法有没有关系？我们定义dp[i]表示数字i的不同划分方法，那么dp[n+1]与dp[n]的关系是什么？在直观上考虑：n+1和n在大小上相差1，因此n+1和n的划分关系是：

n+1比n多了一种n+1本身
n+1将1拿出来，剩下的等同于n的划分
拿出来的1，可以与n的某些划分的中的数合并，可以得到新的划分。我们来考察n+1的划分
- n+1：(n,1) , (n-1,2) , (n-2,3) , (n-3,4) , (n-4,5) ···((n+1)/2,(n+1)/2) ，其中()表示一种划分，括号中的前一个数是怎么划分的不管，后一个数就是一个确切的数，并且满足，前一个数的划分的最后一个数≥后一个数。对于n而言，很显然这些划分对于n中都是没有的。因为我们单独枚举了n+1的最后一个数，那么留给前面的数尽管可能在n中存在这样的序列，但是加上了n+1枚举的最后一个数就不可能存在这样的序列了。这样问题就出现了，我们怎么才可能找到到底有多少种？
  因此既然有问题，我们不妨将关系定义为二维：dp[i][j]表示数字i的划分中以 j结尾的划分数量，那么可以定义数字i的划分数量dp[i][0]等于dp[i][1]加到dp[i][i]。那么我们就可以解决了~

实际上当我们定义为二维的时候，我们就可以发现，我们实际上是枚举划分的最后一个位置来分类讨论求解，在分类讨论时，我们将当时的状态数存下来以便于后续转移！

1.1、状态转移方程

初始化dp[i][i]=dp[i][0]=1，表示i本身这种划分。
dp[i][j]+=dp[i-j][m]：其中j>1&&j<=i-j并且m>=j，并且m<=i-j （i-j , j）
dp[i][1]=dp[i-1][0]（减少计算）

1.2、参考代码 O(n³) 超时

#include<bits/stdc++.h>
using namespace  std;
int dp[1001][1001];//不存在的情况划分数为 0
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    dp[1][0]=dp[1][1]=1;
    int p=1e9+7;
    for(int i=2;i<=N;++i){
        dp[i][i]=1;//i的情况
        dp[i][1]=dp[i-1][0];
        dp[i][0]=(dp[i][i]+dp[i][1])%p;//全1的情况
        for(int j=2;j<=i/2;++j){//i的划分中 以j为尾数
            for(int m=j;m<=i-j;++m){//遍历i-j中满足条件的所有可能情况，至少要以j结尾
                dp[i][j]=(dp[i][j]+dp[i-j][m])%p;//只需要i-j的划分以m>=j结尾就行，当然m>i-j就无意义了。
            }
            dp[i][0]=(dp[i][0]+dp[i][j])%p;//累计数量
        }
    }
    cout<<dp[N][0];
    return 0;
}

2、解法二：类似完全背包问题

链接：完全背包问题解析
转化问题去思考：
我们很容易想到的一个点是，实际上我们在划分时，只需要划分的数字集合不一样就行了，也就是数字集合的总和能达到n就行了，而不需要满足所谓的n1>=n2>=n3···这种形式上的顺序要求。那么这个问题就转化成了一个类似完全背包的问题了：

对于1~n，n个数字想象成n个物品，体积大小就是数字大小，物品可以无限次被装。
一个背包只能装满总体积为n的物品。

这个问题就完全被转化成为一个完全背包问题，求体积为n的背包有多少种不同的装物品的情况。

算法：计数类dp,# 计数类dp,算法,算法
而这里转化为求：目标是达到背包最大承重的情况下，选取物品可以无限次，选取物品的不同种类数。

本题和完全背包问题的区别，就变成了是求最大利益，还是求种类数。

1.1、状态转移方程

定义 dp[i][j]表示考虑前i个物品，物品不限量装满体积为j的背包时，可以装物品的不同情况数。
一般的：

for(int i=1;i<=n;++i)//遍历物品
for(int j=0;j<=n;++j)//遍历体积
for(int k=0;k*i<=j;++k)//遍历物品承装次数
	dp[i][j]+=dp[i-1][j-k*i];//物品i可以考虑 k 次

但实际上，根据以上推导可以发现，当考虑前i个物品时，体积为j-i的背包的所有可能情况，加一个物品i，就对应于背包体积为j至少有一个物品i所能对应的所有情况了（因为根据以上循环可知，j-i背包的所有可能情况，包含了没有物品i的情况，以及包含了能有则有物品i的情况，那么将其转移至j背包，j背包就包含了至少有一关i物品所能对应的所有情况了）。优化相当于合并情况，避免重复计算。

不加入物品i时种数：dp[i-1][j]
加入物品i但不限次时种数：dp[i][j-i]
dp[i][j]=dp[i-1][j]+dp[i][j-i]

1.2、解释

不加入物品i时的种数：dp[i-1][j]
加入物品i但不限次数时的种数：dp[i][j-i]

对于这两个状态转移方程，它们分别代表了以下含义：由于一个包含i，一个不包含i，这两种划分必然是互不包含的。

dp[i-1][j]：这表示考虑前i-1种物品（或者说数字），使得整数划分的总和为j的方法数量。在这个状态中，我们不包括第i个物品（或者说数字i），即我们看不包含i能划分成j的种数。
dp[i][j-i]：这表示考虑前i种物品（或者说数字），其中至少包含一个i，使得整数划分的总和为j的方法数量。由于我们考虑的是完全背包问题，即每个数字可以被无限次使用，所以在当前状态下加入i后，总和为j-i的状态可以直接转移到总和为j的状态。简单地说，dp[i][j-i]就是考虑j-i总和时，还能继续加入i以到达j的种数，且这种情况情况至少包含了一个i，即j-i到j的转移，而其余数量的i包含在j-i的划分中。

将这两个状态结合起来，我们得到整数j的总的划分方法数量：

dp[i][j] = dp[i-1][j] + dp[i][j-i]

这个方程结合了两种情况：一种是不包含数字i的划分种数，另一种是至少包含一个数字i的划分种数。这两种情况构成了所有可能的情况。

为了清晰起见，假设我们有一个整数划分问题，要将数字5分解为不大于5的整数之和。使用上面的状态转移方程：

如果我们不使用数字5，那么dp[5][5]需要包含不使用5得到5的所有方法，即dp[4][5]。
如果我们至少使用一个5，那么我们看在不超过5的情况下，有多少种方法得到0，这是一个空划分，只有一种方式，所以dp[5][5]还要加上dp[5][0]。

这样，dp[5][5]就等于dp[4][5]（不使用5的方法）加上dp[5][0]（至少使用一个5的方法）。当然，dp[5][0]在这种情况下是1，因为只有一种方法用5得到5。

这就是为什么整数划分问题在考虑加入物品（或数字）时使用的是dp[i][j-i]，它反映了完全背包中的无限使用特性。

1.3、降维优化

背包问题降维优化是很简单的，因为每次使用只使用之前的，因此可以降维:文章来源地址https://www.toymoban.com/news/detail-851857.html

for(int i=1;i<=n;++i)//遍历物品i
	for(int j=i;j<=n;++j)//遍历背包大小，从小到大遍历，因为dp[i][j]可以由dp[i][j-i]转移，因此小j需要先计算出来。
		dp[j]=(dp[j]+dp[j-i])%p;
cout<<dp[n];

1.4、参考代码

#include<bits/stdc++.h>
using namespace  std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    int dp[1001]={};
    dp[0]=1;
    int p=1e9+7;
    for(int i=1;i<=N;++i){
        for(int j=i;j<=N;++j)
            dp[j]=(dp[j]+dp[j-i])%p;
    }
    cout<<dp[N];
    return 0;
}