算法：计数类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的基本思路涉及以下几个步骤：

1. 定义状态：根据问题的特性，合理定义状态，表示达到当前状态的可能情况数量。状态通常涉及考虑的元素个数、已选择元素的性质（如总和、最大值等）以及其他约束条件。

2. 确定状态转移方程：根据问题的性质，确定从已知状态到未知状态的转移方式。状态转移方程描述了在当前决策下，如何通过之前的状态来计算当前状态的值。

3. 初始化：正确初始化DP数组，特别是基础情况（通常是递归的边界条件），这些基础情况直接决定了递推的起点。

4. 计算顺序：根据状态之间的依赖关系确定计算顺序，确保在计算某个状态之前，它依赖的状态已经被计算。

5. 结果汇总：根据问题要求，从DP数组中提取最终结果。有时可能需要遍历DP数组的某些部分来汇总最终的计数结果。

三、典型例题

一、ACWing：900. 整数划分

900. 整数划分

  这类问题的难点再于找到状态和状态转移方程，以及看出来它是一个动态规划题。

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的背包有多少种不同的装物品的情况。

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

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考虑的所有次数了。因为dp[i][j-i]已经考虑了所有可能的种类数情况，相当于合并。

• 不加入物品i时种数：dp[i-1][j]

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

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