两个数组的动态规划问题：从入门到精通
1. 引言：为什么关注两个数组的DP
在算法竞赛和面试中，涉及两个序列（字符串、数组）的动态规划问题是一类极其经典且高频的题型。它们的核心思想是将两个序列的匹配、对齐、转换等操作，通过一个二维的状态表进行递推。
这类问题的魅力在于：
-
高度抽象：将现实中的“编辑文本”、“比较基因序列”、“匹配URL”等问题抽象为数学上的序列操作。
-
结构清晰：通常状态定义
dp[i][j]表示第一个数组的前i个元素和第二个数组的前j个元素之间的关系。 -
难度梯度明显：从简单的 LCS（最长公共子序列）到复杂的正则匹配，覆盖了从入门到困难的各个层次。
掌握好这一类问题，不仅能在面试中应对自如，更能深刻理解动态规划中“状态空间”和“决策过程”的核心思想。
2. 动态规划基础回顾
在深入双数组DP之前，我们有必要回顾动态规划的核心思想。
2.1 DP三要素
-
状态 (State)：定义子问题的解。对于双数组问题，标准状态是
dp[i][j]，通常表示：-
nums1[0..i-1]和nums2[0..j-1]的某种性质。 -
注意：我们通常使用
i表示长度（前i个），而不是索引，这有助于处理空字符串的情况。
-
-
转移方程 (Transition)：描述如何从较小的子问题推导出当前问题。通常基于
nums1[i-1]和nums2[j-1]是否相等，或者进行某种操作。 -
边界条件 (Base Case)：通常涉及一个数组为空的情况，即
dp[0][j]和dp[i][0]。
2.2 二维DP表的构建哲学
对于两个数组的问题，我们往往将第一个数组放在行方向，第二个数组放在列方向，形成一个二维表格。
-
行 (i)：处理第一个数组的前缀。
-
列 (j)：处理第二个数组的前缀。
-
目标：通常最终答案是
dp[m][n]。
思考路径：当我们站在 (i, j) 这个格子时，我们只关心“当前这对元素”的匹配情况，以及“之前”已经计算好的前缀状态。
3. 经典模型一：最长公共子序列 (LCS)
最长公共子序列（Longest Common Subsequence）是双数组DP的“Hello World”。
3.1 问题定义与直觉
问题：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
-
子序列：不要求连续，但相对顺序不变。
-
与子串的区别：子串要求连续。
直觉：我们尝试逐个字符匹配。如果两个字符相等，那么它肯定可以成为公共子序列的一部分。如果不相等，我们有两种选择：要么跳过 text1 的当前字符，要么跳过 text2 的当前字符。
3.2 状态定义与转移方程
定义：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。
转移方程：
-
如果
text1[i-1] == text2[j-1]：
这两个字符可以配对。那么dp[i][j] = dp[i-1][j-1] + 1。
解释：我们在两个字符串都去掉最后一个字符的最优解上，加上这个相等的字符。 -
如果
text1[i-1] != text2[j-1]：
我们无法同时使用这两个字符。我们需要看看去掉text1的最后一个字符，或者去掉text2的最后一个字符，哪个能获得更大的LCS。dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
边界条件：dp[0][j] = 0，dp[i][0] = 0。因为只要有一个字符串为空，公共子序列长度就是 0。
3.3 代码实现与空间优化
基础实现（二维）：
python
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
空间优化（滚动数组）：
观察转移方程，dp[i][j] 只依赖于 dp[i-1][j-1]，dp[i-1][j] 和 dp[i][j-1]。也就是说，计算当前行 i 只需要上一行 i-1 和当前行 i 的前一个元素。因此我们可以将空间复杂度从 O(m*n) 优化到 O(min(m, n))。
python
def longestCommonSubsequence(text1: str, text2: str) -> int:
if len(text1) < len(text2):
text1, text2 = text2, text1 # 确保短的作为列，减少空间
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0 # 相当于 dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # 保存旧的 dp[j] (即 dp[i-1][j]) 以便下一轮使用
if text1[i-1] == text2[j-1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j-1]) # dp[j] 是旧的 (i-1, j), dp[j-1] 是新的 (i, j-1)
prev = temp
return dp[n]
3.4 打印所有LCS
要打印出具体的LCS字符串，我们需要回溯。通常我们需要一个 dp 表，从 (m, n) 反向走到 (0, 0)。
-
如果
text1[i-1] == text2[j-1]，则该字符属于LCS，加入结果，向(i-1, j-1)移动。 -
否则，比较
dp[i-1][j]和dp[i][j-1]，向较大的方向移动。如果相等，说明存在多条路径，可以分别处理。
3.5 变体：最长公共子串
问题：最长公共子串要求连续。
状态定义：dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串的长度。
转移方程：
-
如果
text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。 -
如果不相等，则
dp[i][j] = 0。 -
答案：遍历过程中的最大值。
注意：这里 dp[i][j] 的定义与LCS不同，它强制要求以当前字符结尾，因此状态转移更直接，但最终答案不是 dp[m][n]，而是最大值。
4. 经典模型二：编辑距离 (Levenshtein Distance)
编辑距离是衡量两个字符串相似度的经典算法，广泛应用于拼写检查、DNA序列比对等场景。
4.1 问题定义与操作
问题：给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：
-
插入一个字符
-
删除一个字符
-
替换一个字符
4.2 状态设计与转移
状态定义：dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。
边界条件：
-
dp[0][j] = j：将空串转为word2前j个字符，需要插入j次。 -
dp[i][0] = i：将word1前i个字符转为空串，需要删除i次。
转移方程（考虑 word1[i-1] 和 word2[j-1]）：
-
如果
word1[i-1] == word2[j-1]：
不需要任何操作，直接继承之前的距离。dp[i][j] = dp[i-1][j-1] -
如果
word1[i-1] != word2[j-1]：
我们可以执行三种操作，取最小值：-
删除：删除
word1[i-1]，然后让word1[0..i-2]去匹配word2[0..j-1]，代价是dp[i-1][j] + 1。 -
插入：在
word1中插入一个字符等于word2[j-1]，然后让word1[0..i-1]去匹配word2[0..j-2]，代价是dp[i][j-1] + 1。 -
替换：将
word1[i-1]替换为word2[j-1]，代价是dp[i-1][j-1] + 1。
所以：
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 -
4.3 代码实现与理解
python
def minDistance(word1: str, word2: str) -> int:
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):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
return dp[m][n]
理解：编辑距离表是一个典型的“编辑图”。每一步决策都试图最小化操作次数。
4.4 变体：只有插入和删除、一次编辑距离
-
只有插入和删除：实际上，如果只有插入和删除，那么替换操作等价于一次删除加一次插入，代价为2。但如果我们允许替换代价为1，则问题退化回编辑距离。如果操作只有插入和删除（比如在DNA比对中，替换视为删除+插入），我们修改转移方程即可。
-
一次编辑距离：判断两个字符串是否只需要一次操作就能相等。可以利用双指针线性扫描，复杂度
O(n)，不需要完整DP。
5. 经典模型三：交错字符串 (Interleaving String)
交错字符串问题考察的是对字符串顺序的严格匹配。
5.1 问题定义
给定三个字符串 s1, s2, s3，验证 s3 是否由 s1 和 s2 交错组成。
交错的定义：s3 的字符顺序必须保持 s1 和 s2 各自的相对顺序，且 s3 恰好包含 s1 和 s2 的所有字符。
状态定义：dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。
转移方程：dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
-
边界：
dp[0][0] = True。 -
dp[i][0]：只由s1匹配s3，需检查s1[0..i-1] == s3[0..i-1]。 -
dp[0][j]：同理。
优化：可以使用一维DP，因为 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-1]。
python
def isInterleave(s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
m, n = len(s1), len(s2)
dp = [False] * (n + 1)
dp[0] = True
for j in range(1, n + 1):
dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
for i in range(1, m + 1):
dp[0] = dp[0] and s1[i-1] == s3[i-1]
for j in range(1, n + 1):
dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])
return dp[n]
6. 经典模型四：正则表达式与通配符匹配
这两道题是双数组DP中难度较高的代表，难点在于处理 * 的零次或多次匹配。
6.1 通配符匹配 (Wildcard Matching)
问题：实现支持 ? 和 * 的通配符匹配。
-
?匹配任意单个字符。 -
*匹配任意字符序列（包括空序列）。
状态定义：dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。
转移方程：
-
如果
p[j-1] == '?'或p[j-1] == s[i-1]：dp[i][j] = dp[i-1][j-1] -
如果
p[j-1] == '*'：-
*匹配空序列：dp[i][j-1] -
*匹配至少一个字符：dp[i-1][j]
所以dp[i][j] = dp[i][j-1] or dp[i-1][j]
-
边界：
-
dp[0][0] = True -
dp[0][j]：只有当p[0..j-1]全是*时才为 True。 -
dp[i][0] = Falsefor i > 0。
6.2 正则表达式匹配 (Regular Expression Matching)
问题：实现支持 . 和 * 的正则匹配。
-
.匹配任意单个字符。 -
*匹配前面那个字符的零次或多次出现。
区别：这里的 * 是依附于前一个字符的，复杂度更高。
状态定义：dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。
转移方程：
-
如果
p[j-1]是普通字符或.，且s[i-1] == p[j-1]或p[j-1] == '.'：dp[i][j] = dp[i-1][j-1] -
如果
p[j-1] == '*'：
我们需要看p[j-2]是什么。-
匹配零次：忽略
p[j-2]和*，即dp[i][j-2]。 -
匹配一次或多次：前提是
s[i-1]与p[j-2]匹配（p[j-2] == '.'或p[j-2] == s[i-1]），那么dp[i-1][j]（保持模式中的*，消耗一个字符）。
所以：
dp[i][j] = dp[i][j-2] or ( (s[i-1] == p[j-2] or p[j-2] == '.') and dp[i-1][j] ) -
边界：
-
dp[0][0] = True -
dp[0][j]：需要处理a*b*c*这样的模式，即偶数位为*时可以匹配空。
6.3 难点：* 的零次或多次匹配
理解 * 的转移是正则匹配的关键。dp[i][j] 依赖 dp[i][j-2]（零次）和 dp[i-1][j]（多次）。这种依赖关系使得填表顺序至关重要：i 从小到大，j 从小到大，且 j 的循环中需要能访问到 dp[i][j-2]。
7. 经典模型五：两个数组的最大路径和 / 最小路径和
虽然严格来说是一个二维网格问题，但可以看作是第一个数组（行索引）和第二个数组（列索引）的组合。
7.1 网格路径问题（二维）
问题：给定一个 m x n 的网格，每个格子有一个非负整数，找一条从左上角到右下角的路径，使得路径上的数字总和最小（或最大）。每次只能向下或向右移动。
状态：dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。
转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
这本质上是将两个“数组”（行和列）组合起来。
7.2 带障碍物的路径
如果网格中有障碍物，dp[i][j] = 0 如果 grid[i][j] == 1，否则转移同上。
7.3 两个数组的独特路径转化为网格
有时候问题看似是两个数组，实际上是网格上的路径问题。例如，给定两个数组，每次可以从一个数组取头元素，问取完所有元素的顺序有多少种。这可以映射为网格路径计数问题。
8. 高级技巧与优化
8.1 空间优化：滚动数组
绝大多数双数组DP问题，状态转移只依赖于当前行和上一行（或者上一行和当前行的前一列）。因此我们可以将 dp[m+1][n+1] 优化为 dp[2][n+1] 或 dp[n+1]。
-
LCS：依赖
i-1,j-1（左上），i-1,j（上），i,j-1（左）。使用一维数组时，需要用一个变量保存左上角的值。 -
编辑距离：同样可以压缩为一维，注意覆盖顺序。
8.2 时间优化：四边形不等式、单调队列
对于某些特定形式的DP（如 dp[i][j] = min(dp[i-1][k] + cost(k, j))），可以利用四边形不等式进行决策单调性优化，将 O(n^3) 降到 O(n^2)。但在双数组标准模型中较少见。
8.3 位运算优化 (Bitset LCS)
对于字符集较小（如DNA序列，只有4种字符）且长度较长的LCS问题，可以使用位运算进行加速。通过将每一行状态表示为位集，利用位运算实现快速转移，复杂度可以降到 O(m * n / word_size)，如使用 bitset。
8.4 记忆化搜索 vs 迭代DP
对于复杂的状态转移（如正则匹配），记忆化搜索（递归+备忘录）通常更容易理解和实现，且不需要考虑填表顺序。缺点是递归栈开销。迭代DP性能更好，但需要谨慎处理边界和循环顺序。
9. 实战训练：LeetCode 经典题精讲
9.1 基础篇：718. 最长重复子数组
问题：给两个整数数组，求最长公共子数组（连续）的长度。
分析：与最长公共子串相同，但元素是整数。
状态：dp[i][j] 表示以 A[i-1] 和 B[j-1] 结尾的最长公共子数组长度。
转移：
-
如果
A[i-1] == B[j-1]，dp[i][j] = dp[i-1][j-1] + 1 -
否则
dp[i][j] = 0 -
答案：
max(dp)
复杂度：O(m*n)，空间可优化为一维。
9.2 中等篇：1143. 最长公共子序列
见第3章，这是LCS的标准题。
9.3 进阶篇：72. 编辑距离
见第4章。
9.4 复杂篇：10. 正则表达式匹配
见第6.2节。
关键点：处理 * 时的零次和多次匹配。注意初始化 dp[0][j] 对于模式中 * 的处理。
python
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# 初始化空串与模式匹配的情况
for j in range(1, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j-1] == '.' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-2] # 匹配零次
if p[j-2] == '.' or p[j-2] == s[i-1]:
dp[i][j] = dp[i][j] or dp[i-1][j] # 匹配一次或多次
return dp[m][n]
9.5 其他：97. 交错字符串、44. 通配符匹配
交错字符串（第5章）和通配符匹配（第6.1章）都是常见考题。
10. 思维框架：如何攻克双数组DP
当你在面试或竞赛中遇到双数组DP问题时，可以按照以下步骤思考：
10.1 识别模型
-
比较/匹配类：LCS、编辑距离、正则匹配。
-
路径类：网格路径、交错字符串。
-
子数组类：最长公共子串、最大子段和（但扩展到两个数组）。
10.2 状态定义五步法
-
前缀思想：几乎总是
dp[i][j]表示第一个数组的前i个元素和第二个数组的前j个元素的结果。 -
明确含义：是“长度”、“是否可行”、“最小值”还是“最大值”？
-
结尾与否：是否强制以当前元素结尾？对于子数组问题需要，对于子序列不需要。
-
维度确认：二维通常足够。如果涉及更复杂的约束，可能需要三维（如同时考虑字符位置和匹配状态）。
-
目标位置：最终答案通常是
dp[m][n]，也可能是遍历中的最大值。
10.3 边界条件与初始化
-
dp[0][j]：第一个数组为空时的处理。 -
dp[i][0]：第二个数组为空时的处理。 -
dp[0][0]：基础情况。
常见初始化：
-
LCS：全0。
-
编辑距离：
dp[i][0]=i, dp[0][j]=j。 -
正则匹配：需要处理
*匹配空的情况。
10.4 转移的依赖关系
-
相等情况：通常依赖
dp[i-1][j-1]。 -
不等情况：可能依赖
dp[i-1][j]、dp[i][j-1]，或进行替换、插入、删除操作。 -
*情况：依赖dp[i][j-2]和dp[i-1][j]，依赖方向需要注意。
填表顺序：
-
通常
i从1到m，j从1到n。 -
如果转移依赖
dp[i][j-2]，j必须从小到大，保证j-2已计算。 -
如果依赖
dp[i-1][j]，i必须从小到大。
10.5 优化与实现
-
先写出二维DP，确保正确性。
-
再根据依赖关系尝试空间优化为滚动数组。
-
如果时间复杂度过高，考虑是否有特殊性质（如字符集小、位运算优化）。
11. 总结与拓展
两个数组的动态规划问题是算法世界的瑰宝。从基础的 LCS 到复杂的正则匹配，它们体现了动态规划处理序列问题的通用框架。
掌握这些模型的意义：
-
面试必备：几乎所有大厂的算法面试都会涉及至少一道双数组DP题。
-
思维训练：培养将复杂问题分解为子问题、定义状态、寻找递推关系的能力。
-
现实应用：文本差异比较（Git diff）、生物信息学（基因序列比对）、自然语言处理（句子相似度）等领域都基于这些算法。
拓展方向：
-
三维DP：当涉及两个数组外加一个状态（如匹配次数、剩余能量）时，需要三维状态。
-
KMP优化：对于某些特定模式匹配的DP，可以结合KMP自动机优化。
-
分治优化：对于某些DP，可以用分治法（如Divide and Conquer DP Optimization）优化。
-
非序列双数组：有时两个数组并不是字符串，而是具有数值或特殊结构，但思想相通。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
0
0- 0
已为社区贡献68条内容
所有评论(0)