基于0索引的Edit Distance解法在CSES上出错，请求排查问题

错误核心 #

你的DP初始化逻辑存在错误，仅考虑了删除当前字符的操作，忽略了保留当前字符并删除前面所有字符的更优情况，导致部分测试用例计算出的编辑距离偏大。

具体错误示例 #

比如输入s="ba"，t="a"：

• 你的代码计算dp[0][0] = cost(0,0) = 1（b≠a）
• dp[1][0] = dp[0][0] + 1 = 2，但正确的最小编辑距离应为1（直接删除b即可得到a）。

问题根源 #

你定义dp[i][j]为s[0..i]转换为t[0..j]的最小编辑距离，但初始化第一列时，仅通过dp[i][0] = dp[i-1][0] + 1累加删除操作的成本，默认必须保留s[0]并删除后续字符，却忽略了可以选择保留s[i]、删除前面所有字符的更优路径。

修正方案 #

改用编辑距离问题的标准DP定义：dp[i][j]表示s的前i个字符（s[0]到s[i-1]）转换为t的前j个字符（t[0]到t[j-1]）的最小编辑距离。这种定义下初始化和转移逻辑更清晰，且能覆盖所有最优操作：

1. 数组大小：dp数组大小设为(s.size()+1) x (t.size()+1)，对应空字符串到完整字符串的所有前缀组合。
2. 初始化：
   • dp[i][0] = i：将s的前i个字符转为空字符串，需要删除i次。
   • dp[0][j] = j：将空字符串转为t的前j个字符，需要插入j次。
3. 转移方程：
   • 若s[i-1] == t[j-1]，则无需替换，dp[i][j] = dp[i-1][j-1]
   • 否则取三种操作的最小值：替换（dp[i-1][j-1]+1）、删除s[i-1]（dp[i-1][j]+1）、插入t[j-1]（dp[i][j-1]+1）

修正后的代码 #

#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    // 初始化空字符串相关状态
    for (int i = 1; i <= n; ++i) dp[i][0] = i;
    for (int j = 1; j <= m; ++j) dp[0][j] = j;
    
    // 填充DP表
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min({dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1});
            }
        }
    }
    
    cout << dp[n][m] << endl;
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

内容的提问来源于stack exchange，提问作者Shaurya Parashar