首先我为我糟糕的英语道歉。
最近，我遇到了一些关于两种类型的动态编程的令人困惑的事情。
在"；最长公共子序列"；问题如果char不相等，那么我们取两个子问题之间的最大值。另一方面；编辑距离"；问题，如果字符不相等，那么我们取三个子问题中的最小值。
我的问题是为什么我们取三个子问题的最小值
为什么我们不取两个子问题中的最小值，比如最长公共子序列？
选择的数量不同，因为这两个问题的性质不同。
对于Levenstein距离(您所指的编辑距离(，这三个选项对应于三种可能的操作。当计算lev[i][j]时，对应于子串a[1..i]和b[1..j]，如果是a[i] != b[j]，则三个选项为：
d[i][j-1]，它将a[1..i]转换为b[1..j-1]，然后插入b[j]d[i-1][j]，将a[1..i-1]转换为b[1..j]，然后删除a[i]d[i-1][j-1]将a[1..i-1]转换为b[1..j-1]，然后用b[j]替换a[i]
如果忽略第三个选项，则表示您正在计算不同的编辑距离，该距离只允许插入和删除。事实上，这种编辑距离与LCS问题密切相关。具体地说，如果字符串的长度分别是m和n，那么这个受限制的编辑距离将是
D = m + n - 2 * LCS(a, b)
这个等式成立是因为，为了仅使用插入和删除将a转换为b，您必须：
- 删除
a中除LCS中的字符外的所有字符(因此m - LCS(a,b)操作( - 插入除了LCS中的字符之外的
b的所有字符(因此n - LCS(a,b)操作(