力扣72-编辑距离

题目链接

记忆化搜索：
解题关键：每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示）
临界条件：当 i 或 j 小于0时，表示该字符串为空，编辑距离确定为 y+1 或 x+1

int dp[501][501]={0};
class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(),n=word2.size();for(int i=0;i<m;i++)for(int j=0;j<n;j++)dp[i][j]=INT_MAX;return dfs(m-1,n-1,word1,word2);}int dfs(int x,int y,string word1,string word2){if(x<0)return y+1;if(y<0)return x+1;if(dp[x][y]!=INT_MAX)return dp[x][y];if(word1[x]==word2[y])return dfs(x-1,y-1,word1,word2);int ans= min(min(dfs(x-1,y,word1,word2),dfs(x,y-1,word1,word2)),dfs(x-1,y-1,word1,word2))+1;dp[x][y]=ans;return ans;}
};

动态规划（区间dp）
由状态转移方程直接推得,自底向上
转移方程：dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1 此处 i / j 表示剩余待匹配长度

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();//dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1vector<vector<int>>dp(n+1, vector<int>(m+1, INT_MAX));//dp[i][0] = i  and dp[0][j] = jfor(int i=0;i<=n;i++){dp[i][0] = i;}for(int j=0;j<=m;j++){dp[0][j] = j;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(word1[i-1]==word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] =min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;}}}return dp[n][m];}
};