动态规划编辑距离

前言

问题描述：
给定两个字符串 word1 和 word2，请计算将 word1 转换为 word2 所需的最小操作数量。
你可以对单个单词执行以下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

注意： 首先我们要明确一点, 即我们将 word1 转换为 word2, 因此我们必须采取上述三种措施针对 word1 而不是 word2, 由于此前有不少文章对此问题阐述不够清晰, 致使诸多读者在理解本题时产生了一定障碍。

探讨动态规划求解的具体步骤的文章对此篇文章的看法较为积极：https://zhuanlan.zhihu.com/p/91582909]

问题分析

DP问题的求解通常包含三个关键步骤：首先明确各个数组单元所代表的具体内容；其次确定初始条件；最后建立各数组单元之间的相互联系。

• 定义数组元素的含义

此步骤中对dp[i][j]的定义相对直接。dp[i][j] 表示为word1经过一系列操作后将前i个字符转化为word2的前j个字符所需的最小操作次数。尽管如此，我们必须深入理解这一数组的意义。由于对其中概念的理解存在偏差，导致我曾几度对该问题无从下手。需要注意的是，在定义中i与j分别代表什么呢？即只需将word1的前i个字符转化为word2的前j个字符即可，并不需要关心后续未