双序型
双序型
有两个序列/字符串，需要进行一些操作
每个序列本身是一维的，可以转化为二维动态规划
常见是匹配型，也有双区间的
两个字符串的匹配值依赖于两个字符串前缀的匹配值
字符串长度为 n,m 则需要开(n+1)x(m+1)的状态数组
要初始化dp[i][0]与dp[0][i]
通常都可以用滚动数组进行空间优化
也可以用滚动数组优化
两个一维序列/字符串
突破口
- 串A和串B的最后一个字符是否匹配
- 是否需要串A/串B的最后一个字符
- 缩减问题规模
状态：f[i][j]数组下标表示序列A前i个，序列B前j个
初始条件和边界情况
- 空串如何处理
- 计数型（情况1+情况2+.…）以及最值型(min/max情况1，情况2，.…}》
匹配的情况下勿忘+1（操作数多1次，匹配长度多1）
Longest Common Subsequence LCS
状态：f[i][j]表示A前i个字符A[0,i-1]和B前j个字符[0,j-1]的最长公共子串的长度
转移：f[i][j]=max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1|A[i-1]==B[j-1]}
边界：f[0][j]=0, f[i][0]=0
优化：可以滚动数组优化到On
Interleaving String 交错字符串
给定三个字符串A, B, X
判断X是否是由A, B交错在一起形成
即A是X的子序列，去掉A后，剩下的字符组成B
状态：f[i][j]表示为X的前i+j个字符是否由A前i个字符和B前j个字符交错形成
转移：f[i][j]=(f[i-1][j]&&x[i+j-1]==A[i-1])||(f[i][j-1]&&x[i+j-1]==B[j-1])
边界：f[0][0]=true
优化：可以滚动数组优化到On
Edit Distance
状态：f[i][j]表示A前i个字符A[0,i-1]和B前j个字符[0,j-1]的Edit Distance
转移：f[i][j]=min{f[i-1][j]+1, f[i][j-1]+1, f[i-1][j-1]+1, f[i-1][j-1]|A[i-1]==B[j-1]}
边界：f[0][j]=0, f[i][0]=0
Distinct Subsequences 不同子序列
状态：f[i][j]表示A前i个字符A[0,i-1]含有B前j个字符[0,j-1]的不同子序列
转移：f[i][j]=f[i-1][j]+f[i-1][j-1]|a[i-1]==b[j-1]
边界：f[i][0]=1
答案：f[0][j]=0, f[i][0]=1
Regular Expression Matching 正则表达式匹配
状态：f[i][j]表示A前i个字符A[0..i-1]和B前j个字符B[0..j-1]能否匹配
转移：f[i][j]=f[i-1][j-1]&&match(a[i-1],b[j-1]), f[i][j-2]||f[i-1][j]&&match(a[i-1],b[j-2])
Wildcard Matching 通配符匹配
状态：f[i][j]表示A前i个字符A[0..i-1]和B前j个字符B[0..j-1]能否匹配
转移：f[i][j]=f[i-1][j-1]&&match(a[i-1],b[j-1]), f[i][j-2]||f[i-1][j]&&match(a[i-1],b[j-2])
最小的窗口子序列(字节)
给定字符串S和T，在字符串S中找到最短子串W，使得T是W的子序列。如果 S 没有包含 T 中的某个字符，则返回空字符串。如果有多个这样的最小长度子串，则 返回一个起点编号最小的。
状态：f[i][j]表示匹配 T串的前j个字符到S中前i个字符的子序列时的匹配起点
转移：f[i][j]=f[i-1][j-1]|s[i]==t[j],f[i-1][j]|s[i]!=t[j]
边界：f[i][1]=i|s[i]==t[1],f[i][0]=-1
答案：min_i{i-dp[i][m]+1|dp[i][m]!=-1]}
窗口长度为i-f[i][m]+1
dp结束后遍历 dp[][T.length()]，若 dp[i][T.length()] != 0， 则此处存在窗口起点 dp[i][T.length()]，窗口长度为 i – dp[i][T.length()] + 1 此时维护最小窗口长度 len 和窗口起点 start ， 答案为:S.substring(start, start + len)