对动态规划中的两类子问题感到困惑
Confused about two types of sub problems in dynamic programming
起初我为我的糟糕英语道歉。
最近我遇到了一些关于两种动态规划的令人困惑的事情。
在“最长公共子序列”问题中，如果字符不相等，那么我们取两个子问题之间的最大值。
另一方面，“编辑距离”问题，如果字符不相等，那么我们取三个子问题中的最小值。
我的问题是为什么我们取三个子问题中的最小值？
为什么我们不取最长公共子序列之类的两个子问题中的最小值？
因为两个问题的性质不同，所以选择的个数不同
对于Levenshtein distance（就是你说的编辑距离），三个选项对应三种可能的操作。在计算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]，然后 将 a[i] 替换为 b[j]。
如果您忽略第三个选项，那么您正在计算不同的编辑距离，一个只允许插入和删除的距离。这个编辑距离实际上与 LCS 问题紧密 connected。具体来说，如果字符串的长度分别为m和n，那么这个限制编辑距离就是
D = m + n - 2 * LCS(a, b)
这个等式成立是因为，为了仅使用插入和删除将 a 转换为 b，您必须：
- 删除
a 除了 LCS 中的所有字符（因此 m - LCS(a,b) 操作）；
- 插入
b 除了 LCS 中的所有字符（因此 n - LCS(a,b) 操作）。
起初我为我的糟糕英语道歉。
最近我遇到了一些关于两种动态规划的令人困惑的事情。
在“最长公共子序列”问题中，如果字符不相等，那么我们取两个子问题之间的最大值。 另一方面，“编辑距离”问题，如果字符不相等，那么我们取三个子问题中的最小值。
我的问题是为什么我们取三个子问题中的最小值？
为什么我们不取最长公共子序列之类的两个子问题中的最小值？
因为两个问题的性质不同，所以选择的个数不同
对于Levenshtein distance（就是你说的编辑距离），三个选项对应三种可能的操作。在计算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]，然后 将a[i]替换为b[j]。
如果您忽略第三个选项，那么您正在计算不同的编辑距离，一个只允许插入和删除的距离。这个编辑距离实际上与 LCS 问题紧密 connected。具体来说，如果字符串的长度分别为m和n，那么这个限制编辑距离就是
D = m + n - 2 * LCS(a, b)
这个等式成立是因为，为了仅使用插入和删除将 a 转换为 b，您必须：
- 删除
a除了 LCS 中的所有字符（因此m - LCS(a,b)操作）； - 插入
b除了 LCS 中的所有字符（因此n - LCS(a,b)操作）。