双序列DP

状态定义和状态转移方程

状态定义：

对于双序列DP，我们对于DP状态的定义是区间型的，也就是对s的前i个chars里和t的前j个chars ，我们进行计算.通常我们把matrix的长度定义为int[]][] dp = new int[len1 + 1][len2 + 1]， 这是因为我们要考虑empty string的情况，所以dp[0][0]在这时表示的就是两个空串的比较。之所以我对两道regex的问题定义成new int[len1][len2]，是因为我想直接用到index来表示区间。这都是可以的。

因为一般来说dp[i][j]的问题只和dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j]有关，所以我们可以用滚动数组来优化空间复杂度。

状态转移方程

对于s的前i个chars和t的前j个chars，我们一般拿s的ith char和t的jth char进行比较。然后 通过较小的状态（一般为dp[i - 1][j]和dp[i][j - 1]来得出当前dp[i][j]的状态。

题目

• Leetcode 392. Is Subsequence
• Leetcode 115. Distinct Subsequences
• Leetcode 72. Edit Distance
• Leetcode 97. Interleaving String (这道题的状态定义是前i个s和前j个t能否组成前(i+j)个target)
• Leetcode 44. Wildcard Matching
• Leetcode 10. Regular Expression Matching
• Leetcode 72. Edit Distance