语音识别机器翻译-编辑距离-动态规划-细腻解析｜Go主题月

概述【Golang主题学习月】周末肝了几道动态规划题，发了一个超细腻的教学版，反响很不错哦，接下来我会使用两种语言进行编码刷题，分别是GO和JAVA，各位菁英们，坚持刷题吧。????今天这道题非常的实用，这道算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法，当然也不难，加油

【Golang主题学习月】周末肝了几道动态规划题，发了一个超细腻的教学版，反响很不错哦，接下来我会使用两种语言进行编码刷题，分别是GO和JAVA，各位菁英们，坚持刷题吧。

???? 今天这道题非常的实用，这道算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法，当然也不难，加油掌握吧！

如果你对动态规划不熟悉，望转到该篇 \color{red}{如果你对动态规划不熟悉，望转到该篇~}如果你对动态规划不熟悉，望转到该篇 

肝了好多天-动态规划十连-超细腻解析｜刷题打卡

什么题可以选择动态规划来做？

1.计数

有多少种方式走到右下角有多少种方法选出k个数是的和是sum

2.求最大值最小值

从左上角走到右下角路径的最大数字和最长上升子序列长度

3.求存在性

取石子游戏,先手是否必胜能不能选出k个数使得和是sumleecode 72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少 *** 作数 。

你可以对一个单词进行如下三种 *** 作：

插入一个字符删除一个字符替换一个字符 

示例 1：

输入：word1 = "horse", word2 = "ros"

输出：3

解释：

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"

输出：5

解释：

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u') 

提示：

0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成

---

--

动态规划四步走~~~ 其实这道题跟最少硬币组合思路差不多，每次遍历都有三种选择(上面链接第二题)

这道题是 word1 转换成 word2 最少 *** 作数，也是三种选择，我们可以用word1去遍历word2，这样一来不就降低复杂度了吗？ 然后接下来着怎么表示这三种选择❤️❤️❤️❤️

2.1. 动态规划组成部分1：确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似数学题中x, y, z代表什么

最后一步

这道题一般求最值题目，考虑动态规划，存储计算过的值。

很明显如果我们由word1去转换word2,在 *** 作中插入和删除其实是等价的，例如word1="AB",word2="B",对于word1删除A和word2插入A是完全等价的，所以我们就可以转换这三种 *** 作：

word1插入、word2插入、word1word2互相修改

在遍历时，需要用word1的每一个字母去遍历word2的每一个字母

假如：word1 = horse word2 = ros

最后一步无非就是字母e去匹配word2的字母s

子问题

上面说到最后一步就是字母e去匹配word2的字母s

如果最后一步需要word1插入：我们可以推导出f[i][j - 1] + 1,因为我们已经知道word1中字母e对应word2字母0的最小转换次数 (遍历的时候已经存在数组里了)，在加上最后这一次插入。

如果最后一步需要word2插入：我们可以推导出f[i - 1][j] + 1,因为我们已经知道word1中字母s对应word2字母s的最小转换次数，在加上最后这一次插入。

如果最后一步需要word1word2互相修改：我们可以推导出f[i - 1][j - 1] + 1,因为我们已经知道word1中字母s对应word2字母0的最小转换次数，在加上最后这一次修改。

如果最后一步本身就相等： 那么f[i - 1][j - 1]，只需要前一步的最小转换次数就可以了。

所以最少的转换次数：

最后一个字母相同: min{f[i -1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1]}

最后一个字母不相同: min{f[i -1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1}

是不是感觉突然就豁然开朗了???????????????????? \color{red}{是不是感觉突然就豁然开朗了????????????????????~}是不是感觉突然就豁然开朗了???????????????????? 

2.2. 动态规划组成部分2：转移方程

设状态f[i][j]为word1转换word2最少转换次数

对于任意的i、j

最后一个字母相同 : f[i][j] = min{f[i -1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1]}

最后一个字母不相同 : f[i][j] = min{f[i -1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1}

2.3. 动态规划组成部分3：初始条件和边界情况

初始条件：如果word1为null，那么word1转换word2就需要word2的长度，同理word2为null，那么word1转换word2就需要word1的长度

因为涉及到最后一步比较，我们在初始化数组通常定义：int[][] D = new int[n + 1][m + 1];

2.4. 动态规划组成部分4：计算顺序

依次word1每个字母遍历word2的每个字母

参考代码

GO语言版

func mindistance(word1 string, word2 string) int {        n1, n2 := len(word1), len(word2)        dp := make([][]int, n1+1)        for i := range dp {            dp[i] = make([]int, n2+1)        }        for i := 0; i <= n1; i++ {            dp[i][0] = i        }        for i := 0; i <= n2; i++ {            dp[0][i] = i        }        w1, w2, f := 0, 0, 0        for i := 1; i <= n1; i++ {            for j := 1; j <= n2; j++ {                w2 = dp[i-1][j]+1 // word2插入                w1 = dp[i][j-1]+1  // word1插入                f = dp[i-1][j-1]   // 修改                if word1[i-1] != word2[j-1] {                    f = dp[i-1][j-1] + 1  // 不同+1                }                dp[i][j] = Min(                        w1,                        w2,                        f)                            }        }        return dp[n1][n2]    }    func Min(args ...int) int {        min := args[0]        for _, item := range args {            if item < min {                min = item            }        }        return min    }复制代码

JAVA版

 public int mindistance(String word1, String word2) {        int n = word1.length();        int m = word2.length();        // 有一个字符串为空串        if (n * m == 0) {            return n + m;        }        // DP 数组        int[][] D = new int[n + 1][m + 1];        // 边界状态初始化        for (int i = 0; i < n + 1; i++) {            D[i][0] = i;        }        for (int j = 0; j < m + 1; j++) {            D[0][j] = j;        }        // 计算所有 DP 值        for (int i = 1; i < n + 1; i++) {            for (int j = 1; j < m + 1; j++) {                int word2Insert = D[i - 1][j] + 1; // word2插入                int word1Insert = D[i][j - 1] + 1;  // word1插入                int left_down = D[i - 1][j - 1]; // 相同修改                if (word1.charat(i - 1) != word2.charat(j - 1)) {                    left_down += 1; // 不同+1                }                D[i][j] = Math.min(word1Insert, Math.min(word2Insert, left_down));            }        }        return D[n][m];    }    @Test    public voID ismindistance() {        int i = mindistance("horse","ros");        Assert.assertNotNull(i);    }复制代码

❤️❤️❤️❤️

非常感谢人才们能看到这里，如果这个文章写得还不错，觉得有点东西的话 求点赞???? 求关注❤️ 求分享???? 对帅气欧巴的我来说真的 非常有用！！！

如果本篇博客有任何错误，请批评指教，不胜感激 ！

文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Note…，更多内容关注公号：汀雨笔记，陆续奉上。

总结

以上是内存溢出为你收集整理的语音识别机器翻译-编辑距离-动态规划-细腻解析｜Go主题月全部内容，希望文章能够帮你解决语音识别机器翻译-编辑距离-动态规划-细腻解析｜Go主题月所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。