双序列型

状态: f[i][j] 表示第一个 sequence 的前 i 个, 与第二个 sequence 的前 j 个的关系
方程: f[i][j] 第 i 个和第 j 个的匹配关系
初始化: f[i][0] 和 f[0][j]
答案: f[m][n]

题目

Longest Common Subsequence

state: f[i][j] 表示前 i 个字符配上前 j 个字符的 LCS 的长度
function:
f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]+1) for A[i-1] == B[j-1]
f[i][j] = max(f[i-1][j], f[i][j-1]) for A[i-1] != B[j-1]

115. Distinct Subsequences

state: f[i][j]: 表示 S 的前 i 个字符中选取 T 的前j 个字符有多少种方案
function:
f[i][j] = f[i-1][j] + f[i-1][j-1] for S[i-1] == T[j-1]
f[i][j] = f[i-1][j] for S[i-1] != T[j-1]

97. Interleaving String

state: f[i][j]: 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否组成 s3 的前 i+j 个字符
fucntion: f[i][j] = (f[i-1][j] && s1[i-1] == s3[i+j-1]) || (f[i][j-1] && s2[j-1] == s3[i+j-1])

10. Regular Expression Matching

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.') , if (p[j-1] != '*')
dp[i][j] = (dp[i][j - 2] || dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'), (p[j-1] == '*')
难点就是*的处理:
dp[i][j - 2]: 表示匹配 0 个, 即直接跳过模式串 a*.
dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'): 匹配当前串, 匹配成功需要前一步也是成功的.

44. Wildcard Matching

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?'), if (p[j - 1] != '*')
dp[i][j] = dp[i][j-1] || dp[i-1][j], if (p[j - 1] == '*')
难点同样在于*的匹配, 如何表示匹配0个或者多个.
dp[i][j-1] --> 表示忽略掉 *, 即要匹配0个.
dp[i-1][j] --> 表示使用*匹配当前的字符, 即忽略掉当前字符

Algorithms