算法总结-动态规划：字符串相关
动态规划(DP)是一种“空间换时间”的算法思想，在有些题目中，使用递归会进行会进行大量的重复计算，因此更耗时，DP 的做法就是记住这些临时结果，下次再用到时不再重新计算，而是直接读取，记录临时结果使用空间，换取了计算量的降低。
DP 依赖于递推式和初始值。DP 解决问题的流程是，首先，定义好状态，以及状态的含义；之后写出递推式；然后确定初始值。在强化学习中，知道了状态转移方程的 MDP 就可以用 DP 解，状态转移方程就是递推式，所以确定递推式很重要，但这往往是最难的一步。DP 可以解的问题满足最优化原理，具有最优子结构，然后还有 MDP 的决策和无后效性。
直接上来就想 DP 的过程往往会想不清楚，所以使用暴力递归 -> 带 memo 的递归 -> DP -> 空间优化(optiona) 的思路，首先思考暴力递归的过程，有利于想清楚问题的状态如何定义，写递归的过程中可以逐渐明确出递推式，已经递归的终止条件；然后把计算结果使用 memo 记录下来，可以简化一部分计算；之后根据前面的过程中明确出的状态定义，递推式，初始条件，就可以比较简单的写出 DP 方法了。
DP 相关的内容有很多，今天先来承接上一篇，总结一下字符串相关的 DP 问题。
LCS(Longest Common Substring)
这个是 DP 的经典问题了(注意和最长公共子序列区分)，这里就不赘述了，直接给出结果：
状态定义：(i, j), 对应两个字符串 s, t 的下标，dp(i, j) 是 s[:i] 与 t[:j] 的最长公共子串长度。
状态转移：
\(dp(i, j) = \left\{
\begin{aligned}
&0 \qquad &i = 0 \quad or \quad j = 0 \\
&dp(i\textrm{-}1, j\textnormal{-}1) + 1 \qquad &s[i] == t[j] \\
&\max(dp(i,j-1), dp(i-1, j)) &\qquad s[i] != t[j]
\end{aligned}
\right.\)
\
上式中包含了初始值。代码写起来也很简单：
def lcs(s, t):
ans = 0
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
ans = max(ans, dp[i][j])
return ans
正则匹配
LeetCode 10.正则匹配('*'和'.') 和 LeetCode 44.正则匹配('?'和'*') 是两道正则匹配的题目，这也是经典题目，我们分别来看。
LeetCode 10.是给定一个目标串 s 和一个模式串 p ，判断两者是否匹配的问题，其中 p 中含有字符'*' 或者 '.'。'*'匹配零次或者多次前面的字符，'.'匹配任意字符。根据这两条性质我们先来思考暴力方法怎么解决。我们需要两个下标 i, j 来表示当前匹配到的位置。对于p中的字符有三种情况：
- 普通的字符，直接判断与 s 对应字符是否匹配
'.'，可以与任意字符匹配'*'，可以匹配零次前一个字符，也可以匹配多次（这里有一次递归分支）- 前一个字符是普通字符，直接匹配
- 前一个字符是
'.'，可以匹配任意字符零次或多次
于是我们可以写出递归的暴力解法如下：
class Solution_10:
def isMatch(self, s: str, p: str) -> bool:
# 暴力解
def foo(i, j):
if i == j == 0:
return True
elif i == 0:
# 处理 a*, .*, a*b* 这种特殊情况
if p[j - 1] == '*':
return foo(i, j - 2)
else:
return False
elif j == 0:
return False
else:
# '*' 字符
if p[j - 1] == '*':
r = foo(i, j - 2)
if p[j - 2] in {'.', s[i - 1]}:
r = r or foo(i - 1, j)
return r
# '.' 直接匹配任意字符
elif p[j - 1] == '.':
return foo(i - 1, j - 1)
# 普通字符，需要判断一下当前字符是否匹配
else:
return s[i - 1] == p[j - 1] and foo(i - 1, j - 1)
return foo(len(s), len(p))
def _isMatch(self, s: str, p: str) -> bool:
# 另一种暴力写法
def match(t, p):
if len(p) == 0:
return not len(t)
r = (len(t) and (p[0] == t[0] or p[0] == '.'))
if len(p) >= 2 and p[1] == '*':
return match(t, p[2:]) or (r and match(t[1:], p))
else:
return r and match(t[1:], p[1:])
return match(s, p)
上面还给出了另外一种暴力的写法，搜索的方向是正向的，这里利用了python的切片，但是这种写法状态定义不明确，需要明确状态后才能进行下一步，转化为带memo的递归。
转换为带memo的递归步骤很简单，就是在计算之前判断 memo 中是否有结果，有直接返回，没有的话进行计算，在计算完成之后，先把结果存到 memo 中再返回，代码如下。
class Solution_10:
def isMatch(self, s: str, p: str) -> bool:
# 把第一种暴力解转换为 带 memo 的递归搜索
memo = {}
def foo(i, j):
nonlocal memo
if (i, j) in memo:
return memo[(i, j)]
if i == j == 0:
res = True
elif i == 0:
res = foo(i, j - 2) if p[j - 1] == '*' else False
elif j == 0:
res = False
else:
if p[j - 1] == '*':
res = foo(i, j - 2)
if p[j - 2] in {'.', s[i - 1]}:
res = res or foo(i - 1, j)
elif p[j - 1] == '.':
res = foo(i - 1, j - 1)
else:
res = s[i - 1] == p[j - 1] and foo(i - 1, j - 1)
memo[(i, j)] = res
return res
return foo(len(s), len(p))
其实在写出暴力解之后，我们就明确了：
- 递归过程参数 -> 状态
- 递归终止条件 -> 初始值
- 递归调用过程 -> 递推式
然后写出 DP 的过程也就很顺利了, 使用数组表示状态值，然后把递归过程变成递推赋值。注意递推式依赖的值一定是已经被计算过的。在带 memo 的递归时，如果一个状态值还没有被计算，那么会被递归的计算出来，而到了 DP 中使用的是数组，所以我们要在使用它之前确保值是正确的，即合理的安排循环的结构，确保依赖值已经是计算过的。
class Solution_10:
def isMatch(self, s: str, p: str) -> bool:
# 将带 memo 的递归转化为 DP
m, n = len(s), len(p)
dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
dp[0][0] = True
# 处理 a*, .*, a*b* 这种特殊情况
for i in range(1, n + 1):
if p[i - 1] == '*':
dp[0][i] = dp[0][i - 2]
for i in range(1, m + 1):
cs = s[i - 1]
for j in range(1, n + 1):
cp = p[j - 1]
if cp == '*':
dp[i][j] = dp[i][j - 2]
if p[j - 2] in {cs, '.'}:
dp[i][j] = dp[i][j] or dp[i - 1][j]
elif cp == '.':
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = (cs == cp) and dp[i - 1][j - 1]
for x in dp:
print(list(map(int, x)))
return dp[m][n]
接下来进行空间优化，可以看到上面 DP 的代码中，dp[i][j] 依赖于dp[i][j-2], dp[i-1][j] 和 dp[i-1][j-1] 三个值，这只与 i-1 和 i 行有关，因此我们可以将空间优化到两个一维数组滚动进行更新。
class Solution_10:
def isMatch(self, s: str, p: str) -> bool:
# 空间优化
m, n = len(s), len(p)
dp = [False for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
if p[i - 1] == '*':
dp[i] = dp[i - 2]
for i in range(1, m + 1):
cs = s[i - 1]
new_dp = [False for _ in range(n + 1)]
for j in range(1, n + 1):
cp = p[j - 1]
if cp == '*':
new_dp[j] = new_dp[j - 2]
if p[j - 2] in {cs, '.'}:
new_dp[j] = new_dp[j] or dp[j]
elif cp == '.':
new_dp[j] = dp[j - 1]
else:
new_dp[j] = (cs == cp) and dp[j - 1]
dp[:] = new_dp
return dp[n]
对于前面的第二种暴力解法，我们使用下标替代切片作为参数（明确状态）之后可以写出如下的反向过程的 DP 方法。
def isMatch(self, s, p):
# 反向DP
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[-1][-1] = True
for i in range(m, -1, -1):
for j in range(n - 1, -1, -1):
first_match = i < m and p[j] in {s[i], '.'}
if j + 1 < n and p[j + 1] == '*':
dp[i][j] = dp[i][j + 2] or first_match and dp[i + 1][j]
else:
dp[i][j] = first_match and dp[i + 1][j + 1]
return dp[0][0]
LeetCode 44.同样也是给定一个目标串 s 和一个模式串 p ，判断两者是否匹配的问题，其中 p 中含有字符'*' 或者 '?'。'*'匹配任意子串（可以为空），'?'匹配任意字符。两道题目的思路类似，直接给出四个步骤的代码如下。
class Solution_44:
# String, DP, 正则匹配
def isMatch(self, s: str, p: str) -> bool:
# 暴力搜索
def foo(i, j):
if i == j == 0:
return True
elif j == 0:
return False
elif i == 0:
return all(p[t] == '*' for t in range(j))
else:
if p[j - 1] == '*':
return foo(i - 1, j) or foo(i, j - 1)
elif p[j - 1] == '?':
return foo(i - 1, j - 1)
else:
return s[i - 1] == p[j - 1] and foo(i - 1, j - 1)
return foo(len(s), len(p))
def isMatch(self, s: str, p: str) -> bool:
# 带memo 的搜索
memo = {}
def foo(i, j):
nonlocal memo
if (i, j) in memo:
return memo[(i, j)]
if i == j == 0:
res = True
elif j == 0:
res = False
elif i == 0:
res = all(p[t] == '*' for t in range(j))
else:
if p[j - 1] == '*':
res = foo(i - 1, j) or foo(i, j - 1)
elif p[j - 1] == '?':
res = foo(i - 1, j - 1)
else:
res = s[i - 1] == p[j - 1] and foo(i - 1, j - 1)
memo[(i, j)] = res
return res
return foo(len(s), len(p))
def isMatch(self, s: str, p: str) -> bool:
# DP
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(n + 1):
dp[0][j] = all(p[t] == '*' for t in range(j))
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
elif p[j - 1] == '?':
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = s[i - 1] == p[j - 1] and dp[i - 1][j - 1]
return dp[m][n]
def isMatch(self, s: str, p: str) -> bool:
# 空间优化，使用两个数组滚动更新
m, n = len(s), len(p)
dp = [False] * (n + 1)
dp[0] = True
for j in range(n + 1):
dp[j] = all(p[t] == '*' for t in range(j))
for i in range(1, m + 1):
new_dp = [False] * (n + 1)
for j in range(1, n + 1):
if p[j - 1] == '*':
new_dp[j] = dp[j] or new_dp[j - 1]
elif p[j - 1] == '?':
new_dp[j] = dp[j - 1]
else:
new_dp[j] = s[i - 1] == p[j - 1] and dp[j - 1]
dp[:] = new_dp
return dp[n]
括号匹配
括号匹配问题一般使用 Stack 或者计数变量来进行，比如常用应用是将表达式处理成逆波兰式, 遇到左括号入栈，遇到右括号出栈。LeetCode 32.是求最长的括号正确匹配的子串的长度，我们使用 Stack 加上 DP 的思想来做。
我们在栈中存储对应的下标，这样就能在匹配的时候计算匹配的子串长度，因为有 "()()()" 这样的情况，我们使用一个另外的 dp 数组来记录到当前位置匹配的最大长度，这样如果到 i 位置出现了依次匹配，对应的左括号下标为 j 那么此时的最大长度就是 i~j 的长度 i-j+1 再加上 j-1 位置匹配的长度。代码如下。
class Solution_32:
def longestValidParentheses(self, s: str) -> int:
# 括号匹配问题，使用 Stack, 然后使用dp数组来记录状态
stack = []
dp = [0] * len(s)
m = 0
for i, c in enumerate(s):
if c == ')':
if stack:
# 有一对括号 match, 对应的 '(' 的 index 是 j
j = stack.pop()
# 那么到 i 最长的有效匹配的串为
# 从 j 到当前 i 的长度 i - j + 1
# 加上 j 之前已经匹配过的值 dp[j - 1]
dp[i] = i - j + 1 + (dp[j - 1] if j > 0 else 0)
m = max(m, dp[i])
else:
stack.append(i)
return m
这个题目也可使用计数变量来进行。使用 left, right 来分别记录 '(' 和 ')' 出现的次数，我们不需要再使用 Stack, 正反向两次扫描就可以了。扫描过程中，如果 left == right, 即出现 '(' 和 ')' 的次数相等，此时得到了一个括号匹配的串，记录一下长度。
上面是理想的情况，例如对于串 ")))(((" 扫描到最后也是相等的，但是这是一个不匹配的括号。因此，正向扫描中，如果 right 的值大于 left, 即已经多出了一个 ')'，此时左边部分的已经是不匹配的，我们将 left, right 重新置零。从当前位置继续向后扫描。
同样地，反向扫描中，如果 left 的值大于 right, 我们同样将 left, right 重新置零。从当前位置继续向前扫描。
class Solution_32:
def longestValidParentheses(self, s: str) -> int:
# 这不是个 DP 方法，不过更简单
m = 0
# 正向扫描
left = right = 0
for i, c in enumerate(s):
if c == '(':
left += 1
else:
right += 1
if left == right:
m = max(m, left + right)
elif right > left:
left = right = 0
# 反向扫描
left = right = 0
for i in range(len(s)-1, -1, -1):
if s[i] == '(':
left += 1
else:
right += 1
if left == right:
m = max(m, left + right)
elif left > right:
left = right = 0
return m
编辑距离
经典题目 LeetCode 72. 给定两个 word, 可以对第一个 word 进行，插入一个字符/删除一个字符/修改一个字符的操作，求最少多少步可以把第一个 word 变成第二个 word。
我们来思考这个过程，假设两个字符串的长度为 i 和 j，dp(i, j) 表示要把两个字符串变成相等需要的最少步数，那么：
- 如果
i == j == 0, 两个串长度都是0，显然需要0步 - 如果
i == 0, j > 0第一个串的长度为0，则需要插入第二个串的所有字符，步数为j - 如果
i > 0, j == 0，需要删除第一个串中所有字符，步数为i - 如果
i > 0, j > 0，假设我们从右向左进行，这时需要的步数是以下种情况的最小值- 删除第一个字符串的最后一个字符，需要
1 + dp(i-1, j)步 - 插入第二个字符串的最后一个字符，需要
1 + dp(i-1, j)步 - 修改最后一个字符使其相等，需要
dp(i-1, j-1) + word1[i] == word2[j]步
- 删除第一个字符串的最后一个字符，需要
这样就比较清晰了，略去暴力 -> 带 memo 的递归过程，直接给出 DP 代码如下：
class Solution_72:
def minDistance(self, word1: str, word2: str) -> int:
# 状态和状态转移式定义的很清楚了，写出 DP 也很简单
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
f = 1 if word1[i - 1] != word2[j - 1] else 0
dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + f)
return dp[m][n]
子序列拼接与抽取
LeetCode 97. 给两个字符串 s1, s2, 以及一个目标串 s3, 问能否通过将 s1, s2 中的字符穿插（保持原有的字符相对顺序不变）构成目标字符串 s3。
这个题目算是比较简单，对于 s3 中的每一个字符，只能是来自 s1 或者 s2, 因为要保持相对顺序不变，所以我们直接都从前向后就可以了。用 i, j, k 分别表示 s1, s2, s3 的下标，显然对于 s3[k] 有四种情况。
s3[k] == s1[i] == s2[j], 这个字符来自于s1或者s2(这里有一个递归分支)s3[k] == s1[i],s3[k] != s2[j], 这个字符来自于s1。s3[k] == s2[j],s3[k] != s1[i], 这个字符来自于s2。s3[k] != s1[i],s3[k] != s2[j], 这个字符既不是来自s1也不是来自s2，所以不能通过 s1,s2 字符穿插构成 s3。
还有初始值的情况，如果完全匹配到最后一个字符，则最终结果是 True ，如果 s1 或 s2 中一个字符串匹配完了，则结果是 s3 剩下的部分与未匹配完的一个串的剩下的部分是否相同。给出暴力搜索的过程如下。
class Solution_97:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
# 暴力搜索，TLE
if len(s1) + len(s2) != len(s3):
return False
def foo(i, j, k):
if i == len(s1) and j == len(s2) and k == len(s3):
return True # 完全匹配
elif i == len(s1):
# s1 匹配完了，判断 s3 剩余字符是否与 s2 剩余部分相同
return s2[j:] == s3[k:]
elif j == len(s2):
# s2 匹配完了，判断 s3 剩余字符是否与 s1 剩余部分相同
return s1[i:] == s3[k:]
else:
if s1[i] == s2[j] == s3[k]:
return foo(i + 1, j, k + 1) or foo(i, j + 1, k + 1)
elif s1[i] == s3[k]:
return foo(i + 1, j, k + 1)
elif s2[j] == s3[k]:
return foo(i, j + 1, k + 1)
else:
return False
return foo(0, 0, 0)
上述过程转为带 memo 的递归很简单，但是转化为 DP 的时候有一点，这里有 i, j, k 三个状态量，而实际上，有 k = i + j 所以我们可以消去 k 。转换为两个状态量，这样就可以用二维 DP 了， 代码如下。
class Solution_97:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
# 从后向前 DP
if len(s1) + len(s2) != len(s3):
return False
dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
dp[len(s1)][len(s2)] = True
for i in range(len(s1)):
dp[i][len(s2)] = s1[i:] == s3[i + len(s2):]
for j in range(len(s2)):
dp[len(s1)][j] = s2[j:] == s3[len(s1) + j:]
for i in range(len(s1) - 1, -1, -1):
for j in range(len(s2) - 1, -1, -1):
if s1[i] == s2[j] == s3[i + j]:
dp[i][j] = dp[i + 1][j] or dp[i][j + 1]
elif s1[i] == s3[i + j]:
dp[i][j] = dp[i + 1][j]
elif s2[j] == s3[i + j]:
dp[i][j] = dp[i][j + 1]
else:
dp[i][j] = False
return dp[0][0]
值得注意的一点是，dp[i][j] 只与 dp[i+1][j] 或者 dp[i][j+1] 有关，所以可以将空间优化到一维。
class Solution_97:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
# 空间优化
if len(s1) + len(s2) != len(s3):
return False
dp = [False] * (len(s2) + 1)
dp[len(s2)] = True
for i in range(len(s1)):
dp[len(s2)] = s1[i:] == s3[i + len(s2):]
for j in range(len(s2)):
dp[j] = s2[j:] == s3[len(s1) + j:]
for i in range(len(s1) - 1, -1, -1):
for j in range(len(s2) - 1, -1, -1):
if s1[i] == s2[j] == s3[i + j]:
dp[j] = dp[j] or dp[j + 1]
elif s1[i] == s3[i + j]:
dp[j] = dp[j]
elif s2[j] == s3[i + j]:
dp[j] = dp[j + 1]
else:
dp[j] = False
return dp[0]
LeetCode 115. 是给定字符串 s 和 t 求出 s 的子序列组成的字符串等于 t 的不同子序列的数目。
这个题本质上和 97 题是一样的题目，97 题是判断能否用两个字符串组成一个新串，这个题目是能否从串 s 中抽取出一个串 t。用 i，j 分别表示 s 和 t 的下标，对于 s 中的字符 s[i] 如果有 s[i] == s[j] 那么我们可以选 s[i] 或者不选 s[i], 如果 s[i] ！= s[j] 那么我们只能不选 s[i] 将i 向右移动。DP 代码如下，递推式依赖的值要先被计算，所以循环都是从大到小的。
同时给出优化空间的代码，显然 dp[i][j] 只依赖于 dp[i+1][j] 和 dp[i+1][j+1] 。因此，可以直接将空间优化到一维，然后注意要把 j 的循环顺序反过来。
class Solution_115:
def numDistinct(self, s: str, t: str) -> int:
# 反向 DP
m, n = len(s), len(t)
if m==0 or n == 0: # edge case
return 0
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(n, m+1):
dp[i][n] = 1 # 初始值
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
dp[i][j] += dp[i+1][j] # 不选 i 的情况
if s[i]==t[j]:
dp[i][j] += dp[i+1][j+1] # 选 i 的情况
return dp[0][0]
def numDistinct(self, s: str, t: str) -> int:
# 优化空间，注意j的循环要反一下
m, n = len(s), len(t)
if m == 0 or n == 0:
return 0
dp = [0] * (n + 1)
dp[n] = 1
for i in range(m - 1, -1, -1):
for j in range(n):
if s[i] == t[j]:
dp[j] += dp[j + 1]
return dp[0]
子串拼接与拆分
LeetCode 139. 与 LeetCode 140. 是将一个串 s 拆分成给定词典 wordDict 中的字符串的题目。前一个是问能否拆分，后一个是求出所有可能的拆分。
检查能否拆分的思路很简单，我们用 dp[i] 表示从 0 到 i 的子串能够拆分成词典中的字符串，显然如果有 dp[j] 是 True 而且 s[j:i] 是词典中的一个串，那么 dp[i] 就能够被拆分。为了能够快速检索 s[j:i] 是否是词典中的一个串，我们使用一个hash set。于是 DP 过程如下。
class Solution_139:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
memo = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in memo:
dp[i] = True
break # 只要找到一个能够拆分的结果就够了
return dp[len(s)]
上述代码中使用 break 语句来提前终止搜索，对于 LeetCode 140. 我们需要找出所有的可能拆分，就不能再提前终止，而是要搜索出所有的可能，暴力的解法是在递归搜索的过程中记录临时结果，如果找到一个可行的结果，就保存下来。给出带 memo 的递归如下：
class Solution_140:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# 带 memo 的递归, AC
def search(s):
nonlocal memo
res = []
for i in range(len(s)):
left = s[:i + 1]
if left in words:
right = s[i + 1:]
if len(right) == 0:
res.append([left])
return res
if right not in memo:
memo[right] = search(right)
for ls in memo[right]:
res.append([left] + ls)
return res
words = set(wordDict)
memo = {}
res = search(s)
return [' '.join(ls) for ls in res]
我们可以结合 139 题的 DP 过程，先求出 DP 数组，之后根据 DP 数组重建出所有的划分路径。重建路径就是DP的反向过程，我们从最后开始，向前找到一个划分点，然后把后半部分存到临时结果中，继续向前查找，直到找到了一个串 s 的开头，即找到了一个完整的拆分，把结果保存下来（因为是反向查找，所以要取一下反向）。
class Solution_140:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# DP + 重建 path, AC
if len(wordDict) == 0: # edge case
return []
# DP 除了break 其他和 139 题是一样的
mlen = len(max(wordDict, key=len))
memo = set(wordDict)
res = []
dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in memo:
dp[i] = 1
# 重建划分路径
def build_path(left, idx):
nonlocal res, dp, memo
if idx == 0:
res.append(left[::-1])
return
for j in range(max(0, idx - mlen), idx):
w = s[j:idx]
if dp[j] and w in memo:
build_path(left + [w], j)
build_path([], len(s))
return [' '.join(ls) for ls in res]
LeetCode 472. 是给定一个无重复的字符串的 List, 从中找出那些能够使用 list 中其他串拼接而成的字符串。
直观的做法是像对 list 中每一个字符串都像 wordBreak 做一遍check,看是否能够拆分，能够拆分的就是结果集里的。使用 hash set 来降低时间复杂度，代码如下：
class Solution_472:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
def check(w, mm):
for i in range(len(w)):
left, right = w[:i+1], w[i+1:]
if left in mm:
if right in mm or check(right, mm):
return True
return False
memo = set([w for w in words if len(w)]) # 有空串，要排除掉
res = []
for w in words:
if len(w) > 0 and check(w, memo): # 检查串能否被划分
res.append(w)
return res
既然可以像 wordBreak 那样使用递归来解决，那同样也可以使用 DP 来解决， 下面代码中的check 函数部分就和 139 中的 DP 方法一摸一样。
class Solution_472:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
# DP
def check(word, memo):
# 这和 139 的 DP 是完全一样的
dp = [0] * (len(word) + 1)
dp[0] = 1
for i in range(1, len(word) + 1):
for j in range(i):
if dp[j] and word[j:i] in memo:
dp[i] = 1
break
return dp[len(word)]
memo = set(words)
res = []
for w in words:
if len(w) > 0:
memo.remove(w) # 在 check 前先排除自己本身
if check(w, memo):
res.append(w)
memo.add(w)
return res
同时，这一类题目(还有另外一些相关的如 LeetCode 212. wordSearchII) 还有另一种解法，就是使用前缀树（Trie），这不是这篇文的主题，所以留到以后再总结。
其他一些
LeetCode 91.Decode ways. 给一个非空的，由 digit 组成的字符串 s，数字 1 ~ 26 分别对应字母 A ~ Z，求有多少种方式解码这个字符串。
显然一个数字 s[i-1] 应该满足 0 < int(s[i-1]) < 10，两个连续的数字应该满足 10 <= int(s[i-2:i]) <= 26，于是，我们得到如下的 DP 解。
class Solution_91:
def numDecodings(self, s: str) -> int:
# DP
dp = [0] * (len(s) + 1)
dp[0] = 1
# 要么当前位数字在 1~9 之间，可以组成字母映射
# 要么当前两位（加上前一位）在10~26之间，可以组成字母映射
for i in range(1, len(s) + 1):
if 1 <= int(s[i-1]) <= 9:
dp[i] = dp[i - 1]
if i >= 2 and 10 <= int(s[i-2:i]) <= 26: # i-2,i-1
dp[i] += dp[i - 2]
return dp[len(s)]
LeetCode 467. 定义无穷串 s 是由 "abcdefghijklmnopqrstuvwxyz" 无穷拼接而成的，给定一个字符串 p ，求出 p 的非空子串中是 s 的子串的数目。
这题 p 的长度可能超过 10000， $O(n^2)$ 的解会超时，所以要找更好的解。注意到无穷串 s 中任意两个相邻字符都有：(ord(s[i+1]) - ord(s[i])) % 26 == 1 。而且对于 s 的一个子串，例如 "abcd", 它的非空子串同时是 s 的子串的有 {"a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd", "d"}，共 10 个。其中以 'a' 开头的有 4 个，以 'b' 开头的有 3 个，以 'c' 开头的有两个，以 'd' 开头的有一个。显然以字符开头的字串数目等于以这个字符开头的最长子串的长度。所以，我们可以统计以 26 个字母开头的子串的长度，最后求和，就得到了 p 的非空子串中同时是 s 的子串的数目。由于一个字符可能会多次出现，我们只要连续长度最长的一个就好（求max）。
class Solution_467:
# String, DP
def findSubstringInWraproundString(self, p: str) -> int:
res = {c: 1 for c in p}
ln = 1
for i in range(1, len(p)):
ln = ln + 1 if (ord(p[i]) - ord(p[i-1])) % 26 == 1 else 1
res[p[i]] = max(res[p[i]], ln)
print(res)
return sum(res.values())
与字符串有关的 DP 还有一些很难的题目，比如 LeetCode 87. 这是一个 3D 的 DP；以及 LeetCode 943. 这需要转换成图问题（变成图了跟字符串没啥关系了），变成经典的旅行商问题。然后：
I think they don’t really want to hire you if anyone ask you this question during interview.
还有，与字符串有关的 DP 还有回文串相关的一些题目，回文串有一些经典的题目和解法，还有一个神奇的算法 manacher 算法，所以等之后单独来讲。
总结来说，DP 使用记录临时结果的方式来换取时间复杂度的降低，通常依赖于递归状态定义，递推式和初始值，而有些时候直接写出递推式并不容易，所以首先思考递归的解法，通过写递归的过程可以帮助明确 DP 的一些要素，之后再转换为 DP 就要简单一些。按部就班的进行可以帮助理清思路~
DP 还有很多内容，比如各种模型，如线性模型，区间模型，背包模型等。等做了更多的题再来进一步总结吧~
多做题，多总结~