第9章｜动态规划
Unit 12 · LeetCode #72 编辑距离 · 章节终局
每条 DP 入边，
都必须对应一次真实编辑。
本章终局不再满足于“记住三项取最小”。你需要在当前两个前缀中准确解释：上方为什么是删除、左方为什么是插入、左上方为什么是替换；随后再观察一维压缩如何保护被覆盖前的左上角旧值。
已恢复上次学习位置阶段、动画、检查点、代码和迁移进度均已恢复。
知识桥梁｜Unit 11 → Unit 12
Unit 11：比较两个前缀
LCS 在匹配时读取左上角，不匹配时允许丢弃任一末尾字符。
保留二维前缀 → 为边标注操作代价
Unit 12：转换两个前缀
每个状态记录最少编辑次数；三条入边分别表示删除、插入和替换。
本单元贯穿问题当前入边改变了哪个前缀长度？因此它对应哪一种编辑操作？
LeetCode #72 原题题面转述、示例、约束与提交签名
题目要求
给定两个字符串 word1 和 word2，返回把 word1 转换成 word2 所需的最少操作次数。每次允许插入一个字符、删除一个字符或替换一个字符。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
pass
约束
0 ≤ word1.length, word2.length ≤ 500；- 两个字符串只包含小写英文字母。
示例
输入：word1 = "horse", word2 = "ros"
输出：3
一种最优过程：替换 h→r，删除第二个 r，删除 e。
输入：word1 = "intention", word2 = "execution"
输出：5
目标复杂度
二维动态规划时间复杂度 O(mn)、空间复杂度 O(mn)；进一步可压缩到 O(n) 空间。
六段认知流程
本环节已完成
请停留观察当前状态，确认你能解释高亮入边的操作语义。