动态规划学习-编辑距离

mallorJava

实战题目如下（主要借鉴了大佬的解题思路）：




int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
// base case
for (int i = 1; i <= m; i++)
dp[0] = i;
for (int j = 1; j <= n; j++)
dp[0][j] = j;
// &#12163;底向上求解

for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[j] = dp[i - 1][j - 1];
else
dp[j] = min(
dp[i - 1][j] + 1,
dp[j - 1] + 1,
dp[i-1][j-1] + 1
);
// 储存着整个 s1 和 s2 的最&#12073;编辑距离
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));}

wylksy

首先感谢楼主的分享，其次一起学习一起进步。。。。最后遵守版规

ShawnZ

多谢分享。没学过java的我，被动态规划吸引进来。看到int，下意识以为是c语言。。。

mallorJava

ShawnZ 发表于 2021-3-18 08:23
多谢分享。没学过java的我，被动态规划吸引进来。看到int，下意识以为是c语言。。。

感谢老铁支持

mallorJava

wylksy 发表于 2021-3-18 07:40
首先感谢楼主的分享，其次一起学习一起进步。。。。最后遵守版规

第一次发帖，排版有点乱，感谢老铁支持