编辑距离0索引解决方案失败

Question

我在 cses 上实现了一个基于 0 索引的解决方案来解决编辑距离问题，但它对其中一个测试用例给出了错误的答案判断。

#include <bits/stdc++.h>
 
using namespace std;
# define MOD 1000000007
 
string s; string t;
 
int cost(int i,int j){
    return !(s[i] == t[j]);
}
 
void solve() {
    // Write your solution here
    cin>>s; cin>>t;
    vector<vector<int>> dp(s.size(),vector<int>(t.size(),0));
    // dp[i][j] -> the minimum edit distance required to equal A[0-i] and B[0-j]
    dp[0][0] = cost(0,0);
    for (int i=1;i<s.size();i++){
        dp[i][0] = dp[i-1][0] + 1;
    }
    for (int j=1;j<t.size();j++){
        dp[0][j] = dp[0][j-1] + 1; 
    }
    for (int i=1;i<s.size();i++){
        for (int j=1;j<t.size();j++){
            dp[i][j] = min({dp[i-1][j-1] + cost(i,j),dp[i-1][j] + 1, dp[i][j-1] + 1});
            //cout<<dp[i][j]<<" ";
        }
    }
 
    cout<<dp[s.size()-1][t.size() -1];
}   
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t=1;
    //cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
}

由于字符串的最小长度为 1。我不关心包括一个字符串为空的情况。 我将基本情况定义如下。 dp[0][0] -> 通过从字符串 1 中取出第一个字符和从字符串 2 中取出第一个字符形成的字符串的编辑距离。当两个字符相等时，这显然是 0，当两个字符不同时，这显然是 1。 现在，第一栏

for（i 的大小（字符串 1）） dp[i][0] -> dp[i-1][0] + 1

当我不断从一个字符串中获取更多字符，而从另一个字符串中仅获取一个字符时，我只需要在之前的 dp 状态中添加一个字符即可。 第一行也是如此。

失败的测试用例太大，无法手动检查。

有人可以解释一下这可能出了问题吗？

Answer 1

战术错误：动态规划的基础。 通过说

dp[0][0] = cost(0,0)

，您实质上是在说“第一个操作是将

s

的前字母更改为

t

的前字母”。 还有其他可能的操作：删除

s

的前字母并添加

t

的前字母。

战略错误：问题空间。 思考问题的一个好方法是解决子问题。 子问题

(i, j)

的形式为“我们从左到右对所有操作进行排序，并且我们处理了

i

的

s

字母和

j

的

t

字母”。 请注意，子问题对于

0 <= i <= s.size()

和

0 <= j <= t.size()

有效。 所以，问题空间实际上是

(s.size()+1)

乘以

(t.size()+1)

。 而您的代码的两种大小都少了一个。