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];
}
