dp中的正推与逆推

简介

在写dp的题目中常常会涉及到状态转移方程的写法,一般常见的有两种:

  • 正推:由$i$推$i+1$,即去算$i$对之后状态的贡献。
  • 逆推:$i$是由$i-1$推来的,即当前状态是由之前状态推得的。

这两种本质上是没有区别的,但是在写法上略有区别
对于正推,我们要注重它的起点,以及当前的贡献要满足什么条件才能加到之后的状态中去
对于逆推,我们要注重它的边界,一般需要预处理一些边界,还要注意之前的状态能否转移到当前状态

例题

牛牛数括号

题目链接

题目描述

给你两个括号序列,不保证合法,求有多少种不同的方法可以将两个括号序列合并成一个合法的括号序列
合并的时候不能改变各自序列原先的顺序

输入描述

输入两行包含两个字符串s1,s2

1 ≤ |s1|,|s2| ≤ 2500

输出描述

输出一个整数,魔$10^9+7$

解法

首先我们定义x序列为:有可能通过在尾部添加)使得序列合法,注意这里并不只是要满足左括号数量多于右括号,对于)((这样的序列也是不合法的。

设$dp[i][j]$表示$s1$中前$i$个和$s2$中前$j$个,组成x序列的个数
如果i,j都非零,且总左括号数量大于等于右括号数量,那么dp[i][j] > 0

最后的答案:如果两个字符串中左括号的总数等于右括号的总数,那么dp[i][j]就是答案,不然就是0.

正推:

1
2
3
4
5
6
7
dp[0][0] = 1;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(dp[i][j] > 0){
如果(i+1, j)是满足左括号数量减去右括号数量大于0的,那么dp[i+1][j] += dp[i][j];
如果(i, j+1)是满足左括号数量减去右括号数量大于0的,那么dp[i][j+1] += dp[i][j];
}

逆推:

1
2
3
4
5
6
7
8
9
要预处理所有的dp[i][0]和dp[0][i]
要注意并不是左括号数量大于等于右括号数量就为1,)( 这种情况也是不合法的!!!

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i,j) 满足总左括号数量大于总右括号数量){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
// 不需要再去判断之前的状态是否合法,因为如果不合法,其dp值一定是0
}