題目鏈接

記憶化搜索：
解題關鍵：每次僅考慮兩字符串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];}
};