网站 › 『编程语言讨论求助区』 › 动态规划学习-编辑距离

mallorJava 发表于 2021-3-17 23:42

动态规划学习-编辑距离

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




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

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

wylksy 发表于 2021-3-18 07:40

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

ShawnZ 发表于 2021-3-18 08:23

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

mallorJava 发表于 2021-3-18 23:46

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

感谢老铁支持

mallorJava 发表于 2021-3-18 23:47

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

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

查看完整版本: 动态规划学习-编辑距离