https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked
这是一个难题,关于序列DP的,官方的题解较为难懂,这里有一位前辈解释的很好
这里的状态定义是: dp[i][j]表示word1的前i个字母,转换成 word2的前j个字母的最小步数class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// 第一行
for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
// 第一列
for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
return dp[n1][n2];
}
}
标签:String,int,编辑,word1,72,word2,n2,leetcode From: https://www.cnblogs.com/lxl-233/p/18153355