最短编辑距离

tips:

令s2不动，通过对s1进行操作，使其一致
递归式从后往前递推
不管是递归还是迭代，抽象模型都是 s1[0...i]和s2[0...j]是否相同
一共4种操作：
- 如果s1[i] == s2[j]，skip，不作为
- 增，即末尾增加元素，得到上述模型，说明此时 s1[0..i]和s2[0..j-1]已经相同了
- 删，即删除末尾元素，得到上述模型，说明此时 s1[0..i-1]和s2[0..j]已经相同了
- 改，即更改末尾元素，得到上述模型，说明此时 s1[0..i-1]和s2[0..j-1]相同了
由自顶向下递归改写自底向上迭代dp时，每一次递归，对应dp中的下标索引，因为递归时base case情况的存在，即i和j可能是-1，会造成数组下标越界，因此数组整体扩大1
自底向上dp实际上就是打表，把dp表打满答案就出来了，参考labuladongdp表

- 自顶向下递归

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int myMin(int a,int b,int c){
    return min(a,min(b,c));
}

int dp(string& s1,int i, string& s2, int j){
    // 通过dp递归函数，得到s1[0...i]和s2[0...j]的最短编辑距离（倒推）

    // base case
    if( i == -1 ) return j + 1;            // s1已经走完了，s2还剩下
    if( j == -1 ) return i + 1;            // s2已经走完了，s1还剩下

    // 做选择
    if( s1[i] == s2[j] )    // 如果当前字符相等，编辑距离等于前一次的距离
        return dp(s1,i-1,s2,j-1);
    else{
        return myMin( 		dp( s1, i, s2, j - 1 ) + 1,        // 增，s1[0...i]和s2[0...j-1]已相等
                            dp( s1, i - 1, s2, j ) + 1,        // 删，s1[0...i-1]和s2[0...j]已相等
                            dp( s1, i - 1, s2, j - 1 ) + 1     // 改，s1[0...i-1]和s2[0...j-1]相等
                          );
    }

}

int main(){
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int m = s1.size();
    int n = s2.size();
    int res = dp(s1,m-1,s2,n-1);
    cout << res;
}

- 备忘录递归

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

vector<vector<int>> memo;

int myMin(int a,int b,int c){
    return min(a,min(b,c));
}

int dp(string& s1,int i, string& s2, int j){
    // 通过dp递归函数，得到s1[0...i]和s2[0...j]的最短编辑距离（倒推）

    // base case
    if( i == -1 ) return j + 1;            // s1已经走完了，s2还剩下
    if( j == -1 ) return i + 1;            // s2已经走完了，s1还剩下

    // look up memo
    if( memo[i][j] != -1 )        // 之前已经计算过对应的编辑距离
        return memo[i][j];

    // 做选择
    if( s1[i] == s2[j] )    // 如果当前字符相等，编辑距离等于前一次的距离
        memo[i][j] = dp(s1,i-1,s2,j-1);
    else{
        memo[i][j] = myMin( dp( s1, i, s2, j - 1 ) + 1,        // 增，s1[0...i]和s2[0...j-1]已相等
                            dp( s1, i - 1, s2, j ) + 1,        // 删，s1[0...i-1]和s2[0...j]已相等
                            dp( s1, i - 1, s2, j - 1 ) + 1     // 改，s1[0...i-1]和s2[0...j-1]相等
                          );
    }

    return memo[i][j];

}

int main(){
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int m = s1.size();
    int n = s2.size();
    memo = vector<vector<int>>(m,vector<int>(n,-1));
    int res = dp(s1,m-1,s2,n-1);
    cout << res;
}

- 自底向上迭代dp

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<climits>
using namespace std;

// 自底向上迭代dp，由于存在递归i 和 j到-1位置的情况，因此dp数组整体扩大一位

vector<vector<int>> dp;

int myMin(int a,int b,int c){
    return min(a,min(b,c));
}


int main(){
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int res = INT_MAX;
    int m = s1.size();
    int n = s2.size();
    dp = vector<vector<int>>(m+1,vector<int>(n+1,0));
    // base case
    for(int i = 1 ; i <= m ; i++ )
        dp[i][0] = i;
    for(int j = 1 ; j <= n ; j++ )
        dp[0][j] = j;

    for(int i = 1; i <= m ; i ++){
        for(int j = 1 ; j <= n ; j++){
            if( s1[i-1] == s2[j-1] )
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = myMin(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1);
        }
    }

    cout << dp[m][n];


}

alt