java解法： public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); //任意一个字符串为空就返回另一个字符串的长度 if (n * m == 0) { return n + m; } //初始化状态 dp[i][j]表示 从word1的第i个字符变到word2的第j个字符时的变化数 int[][] dp = new int[n + 1][m + 1]; dp[0][0] = 0; for (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++) { //dp[i - 1][j]到dp[i][j]是insert、dp[i][j - 1]是delete、dp[i - 1][j - 1]是replace //replace时 如果相等 说明不用 dp[i][j] = Math.min(Math.min(dp[i - 1][j]+1, word1.charAt(i - 1) == word2.charAt(j - 1) ? dp[i - 1][j - 1] : dp[i - 1][j - 1]+ 1),dp[i][j - 1]+1) ; } } return dp[n][m]; }

编辑距离的状态转移方程 def minDistance(self, word1: str, word2: str) -> int: if not word1 and not word2: return 0 if not word1 or not word2: return len(word1) if word1 else len(word2) h, w = len(word1), len(word2) dp = [[0] * (w+1) for _ in range((h+1))] #加上空字符作为哨兵节点 for i in range(1, len(dp[0])): dp[0][i] = dp[0][i-1] + 1 #初始化第一行，空字符到达每一个非空字符都是+1 for i in range(1, len(dp)): dp[i][0] = dp[i-1][0] + 1 #初始化第一列，空字符到达每一个非空字符都是+1 for i in range(1, len(dp)): for j in range(1, len(dp[0])): if word1[i-1] == word2[j-1]: #相等，编辑距离不增加 dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + 1 # dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作 return dp[-1][-1]

class Solution { public: int minDistance(string word1, string word2) { if(word1.empty()) return word2.size(); if(word2.empty()) return word1.size(); int n1 = word1.size(); int n2 = word2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0)); // dp[i][j] 含义， word1的前i个字符 转化成word2的前j字符最少操作数 // 状态初始化 for(int i = 0; i <= n1; i++){ dp[i][0] = i; } for(int i = 0; i <= n2; i++){ dp[0][i] = i; } for(int i = 1; i <= n1; i++){ for(int j = 1; j <= n2; j++){ if(word1[i-1] == word2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1],dp[i-1][j])) + 1; } } } return dp[n1][n2]; } }; 此刻刚刚昨晚“编辑距离”， 贴代码留个脚印