标准动态规划学习笔记(DNA序列编辑距离)
一、问题核心目标
需要将一个字符串 dna1 转换为另一个字符串 dna2，允许的操作有三种：
- 插入一个字符（从
dna1中添加一个字符到dna2）
- 删除一个字符（从
dna1中删除一个字符）
- 替换一个字符（将
dna1中的某个字符改为dna2中的对应字符）
我们需要找到最小的操作次数。
二、动态规划的本质
动态规划（Dynamic Programming）的核心是将大问题分解为小问题，并存储中间结果避免重复计算。它的关键思想是：
- 定义状态：用一张表（二维数组）表示小问题的解。
- 状态转移：通过状态转移方程，由小问题的解逐步推导出大问题的解。
- 初始化：定义最基础的小问题解。
三、定义状态和表格
假设 dna1 = \"AGT\"（长度为3），dna2 = \"AGCT\"（长度为4）。
我们定义一个二维数组 dp，其中 dp[i][j] 的含义是：
- 将
dna1 的前 i 个字符转换为dna2 的前 j 个字符所需的最小操作次数。
例如：
dp[2][3]表示将AG→AGC的最小操作次数。
dp[3][4]就是最终答案：AGT→AGCT的最小操作次数。
表格形态（行= dna1 的长度+1，列= dna2 的长度+1）：
0
A
G
C
T
0
0
1
2
3
4
A
1
G
2
T
3
四、初始化
初始化表格的边界条件：
1. dna1为空（i=0）
- 只能通过插入操作得到
dna2的前j个字符。
- 例如
dp[0][4] = 4：插入 \"AGCT\"，需要4步。
2. dna2为空（j=0）
- 只能通过删除
dna1的前i个字符。
- 例如
dp[3][0] = 3：删除前3个字符 AGT。
初始后表格：
0
A
G
C
T
0
0
1
2
3
4
A
1
?
?
?
?
G
2
?
?
?
?
T
3
?
?
?
?
五、状态转移方程
填表的核心逻辑——通过已解决的子问题推导当前问题。
1. 若当前字符相等
如果 dna1[i-1] == dna2[j-1]（字符串索引从0开始）：
- 当前字符无需操作，直接继承前一步的值。
- 例如，如果
A → A，则dp[i][j] = dp[i-1][j-1]
2. 若当前字符不等
需要尝试三种操作，并选择代价最小的：
- 删除操作：删除
dna1[i-1]，代价是1 + dp[i-1][j]
- 相当于删除了
dna1的第i个字符，剩下的i-1去匹配j。
- 插入操作：插入
dna2[j-1]，代价是1 + dp[i][j-1]
- 相当于插入
dna2的第j个字符，此时i不变（假装已经插入匹配）。
- 替换操作：替换
dna1[i-1]为dna2[j-1]，代价是1 + dp[i-1][j-1]
- 替换后，两个字符相当于匹配了，下一步处理i-1和j-1。
六、逐步填表分析（以样例为例）
初始表格
0
A
G
C
T
0
0
1
2
3
4
A
1
?
?
?
?
G
2
?
?
?
?
T
3
?
?
?
?
填充 dp[1][1]（i=1，j=1）
- 字符比较：
dna1[0] = \'A\'vsdna2[0] = \'A\'
- 相等→直接继承左上方值
dp[1][1] = dp[0][0] = 0
此时表格：
0
A
G
C
T
0
0
1
2
3
4
A
1
0
?
?
?
G
2
?
?
?
?
T
3
?
?
?
?
填充 dp[1][2]（i=1，j=2）
- 字符比较：
AvsG（不相等）
- 计算三种操作代价：
- 删除A：
1 + dp[0][2] = 1 + 2 = 3
- 插入G：
1 + dp[1][1] = 1 + 0 = 1
- 替换A→G：
1 + dp[0][1] = 1 +1 =2
- 取最小值1（插入操作）
- 意味着：要处理\"A\"转换为\"AG\"，可以通过插入G完成，代价1。
表格更新：
0
A
G
C
T
0
0
1
2
3
4
A
1
0
1
?
?
G
2
?
?
?
?
T
3
?
?
?
?
填充其他格子
以此类推继续填充。最终填完的表如下：
0
A
G
C
T
0
0
1
2
3
4
A
1
0
1
2
3
G
2
1
0
1
2
T
3
2
1
1
1
最后的 dp[3][4] = 1 就是结果。
七、代码走读（以样例为例）
执行 minEditSteps(\"AGT\", \"AGCT\")，核心代码的逻辑如下：
i=3（对应dna1[2] = \'T\'），j=4（对应dna2[3] = \'T\'）。
- 字符相等：
dp[3][4] = dp[2][3] = 1（查表前一步的结果）。
八、动态规划的总结
- 为什么用动态规划？
- 问题允许子问题分解，且存在重叠子问题（例如多次计算相同的子字符串匹配）。
- 例如：
AG → AGC的结果会被多次使用，存储后无需重复计算。
- 如何保证高效？
- 通过表格存储子问题的解，时间复杂度为 O(mn)，空间复杂度可优化到O(n)。
