动态规划解决近似串匹配：kitten 和 sitting 的编辑距离

① dp 数组的含义是记录字符串 'kitten' 和 'sitting' 中每个子串的编辑距离。

② dp 数组的递推公式为：

dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)

其中，dp[i][j] 表示字符串 'kitten' 中前 i 个字符与字符串 'sitting' 中前 j 个字符的编辑距离；cost 表示字符串 'kitten' 中第 i 个字符和字符串 'sitting' 中第 j 个字符是否相同，相同则为 0，不同则为 1。

③ 使用上述递推公式可以得到字符串 'kitten' 和 'sitting' 的编辑距离为 3。具体计算过程如下：

dp 数组初始化为：

0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 0 0 0 0 0 0 2 2 0 0 0 0 0 0 3 3 0 0 0 0 0 0 4 4 0 0 0 0 0 0 5 5 0 0 0 0 0 0 6 6 0 0 0 0 0 0

按递推公式依次填充 dp 数组：

0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 1 2 3 4 5 6 2 2 2 1 2 3 4 5 3 3 3 2 1 2 3 4 4 4 4 3 2 1 2 3 5 5 5 4 3 2 2 3 6 6 6 5 4 3 3 2

最终结果为 dp[6][6]=2+1=3。