chapter_dynamic_programming/edit_distance_problem/

[giscus[bot]]

chapter_dynamic_programming/edit_distance_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_dynamic_programming/edit_distance_problem/

[moshu023]

作者你好，我想问一下文中画图采用的是什么工具呀，感觉很精美。

[krahets]

ppt 和 keynote 都可以

[moshu023]

好的，谢谢作者大大。

[WhiteRhinos]

public static void main(String[] args)
    {
        String target = "hello";
        String result = "a";
        System.out.println(violent(target, result, target.length(), result.length()));
    }

    public static int violent(String target, String result, int ti, int ri)
    {
        if (ti < 1 || ri < 1)
        {
            return Math.max(ti,ri);
        }

        if (target.substring(ti - 1, ti)
                  .equals(result.substring(ri - 1, ri)))
        {
            return violent(target, result, ti - 1, ri - 1);
        }

        int delete = violent(target, result, ti - 1, ri) + 1;
        int insert = violent(target, result, ti, ri - 1) + 1;
        int replace = violent(target, result, ti - 1, ri - 1) + 1;

        return Math.min(delete, Math.min(insert, replace));
    }

[DemingCheng]

大佬可以列一下相关的题单么，谢谢

[krahets]

Krahets 笔面试精选 88 题 ：这里面动态规划专题有一些典型题。
动态规划（基础版）：力扣也有专门的动态规划题单。

[DXShelley]

图14-30中，（i,j） 为（2，2）的时候，图为什么不加一呢？请大佬赐教

[krahets]

因为两字符相等 s[1] = t[1] = 'a' ，此时 dp[i, j] = dp[i-1, j-1]

[mengruibin]

我也想问 字母是a的时候索引不是2嘛图上是这么表示的啊 难道说第一个字母是从索引0开始的？

[mengruibin]

噢我把字符串的索引和dp表的索引混在一起了

[Mingquan-cloud]

我们先考虑两字符串尾部的字符s[n-1]和t[m-1]。

请教一下K神，为什么我们要从字符串尾部开始考虑，是因为这样更便于思考？还是这样才可以将问题规模逐渐缩小呢？

[krahets]

Hi，是的～我们通常习惯于从子问题分解的角度来考虑 dp 问题：原问题 dp[n, m] 是我们最终想得到的结果，一步步分解到更小的子问题，直至基本情况。

[DaiBI5]

是不是可以理解为：思考是向下分节子问题的方向，代码计算的时候是从子问题向上

[ericwzc]

感谢大作！图 14-29, 始终保持t不变，是否应该加上保持s不变的情况呢？状态转移结果是一致的。

[anxiaochou]

他举的例子尾部不同，所以要修改

[ericwzc]

明白了，t是目标字符，所以保持不变

[lwd-coding]

底部向上的思路会比较好想，遍历所有组合然后再找出最小的。从这个代码自然就会联想i,j会定位到一个最小编辑值；而i,j可以有3种情况可以抵达，这样就可以反向写出自上而下的递归进而转成动态放方程

 private static void backtrackBottom(String word1, String word2, int i, int j, int currentDistance) {
        //说明字符串 word1 已经处理完毕，那么剩余的字符是 word2.length() - j，这部分字符需要进行插入操作，所以更新 minDistance 时要加上这个插入的操作数。
        if (i == word1.length()) {
            minDistance = Math.min(minDistance, currentDistance + word2.length() - j);
            return;
        }
        //说明字符串 word2 已经处理完毕，那么剩余的字符是 word1.length() - i，这部分字符需要进行删除操作，所以更新 minDistance 时要加上这个删除的操作数。
        if (j == word2.length()) {
            minDistance = Math.min(minDistance, currentDistance + word1.length() - i);
            return;
        }

        if (word1.charAt(i) == word2.charAt(j)) {
            backtrackBottom(word1, word2, i + 1, j + 1, currentDistance);
        } else {
            // Insert
            backtrackBottom(word1, word2, i, j + 1, currentDistance + 1);
            // Delete
            backtrackBottom(word1, word2, i + 1, j, currentDistance + 1);
            // Replace
            backtrackBottom(word1, word2, i + 1, j + 1, currentDistance + 1);
        }
    }

[2044145178]

想问大佬一件与文章无关的事，这么多种编程语言实现是怎么做到的，是有这方面的转换工具吗

[krahets]

由开源社区小伙伴们一起维护的（这就是开源社区吸引人的地方了）

[macj2010]

暴力搜索也可以，多谢大佬的思路

# 暴力搜索 编辑距离问题，每个字符只能插入、删除、替换一次
def edit_distance_fn(s1: str, s2: str, m: int, n: int) -> int:
    m = len(s1) if m is None else m
    n = len(s2) if n is None else n
    # 边界判断
    if m == 0:
        return n                
    if n == 0:
        return m
    # 递归
    if s1[m-1] == s2[n-1]:
        return edit_distance_fn(s1, s2, m-1, n-1)
    else:
        return 1 + min(edit_distance_fn(s1, s2, m-1, n), edit_distance_fn(s1, s2, m, n-1), edit_distance_fn(s1, s2, m-1, n-1))

[LiHuigui]

可以记忆化搜索呀。

[h-kayotin]

hi，大佬。我遇到一个问题。
输入两个字符串x,y，他们组成n*m的矩阵，计算从(0,0)到(n,m)的最短距离。如果x[j-1]==y[i-1]，就可以走捷径，也就是中间的斜线。
这个问题，看上去就和编辑距离的问题一模一样。同样每一步的[i,j]只可能来自上、左上、或左。
也就是：
if x[j - 1] == y[i - 1]:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
我的问题是，这个要怎么进行空间优化呢？
我试过用保存leftup的方式来优化空间到o(n)，但是好像不行。

[RENHJa]

hi！ 请问
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
为什么用了两层min？在状态转移方程中不是求 dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])三者的最小值吗，那样不是只用一层min就行了吗？

[RENHJa]

是不是因为min这个函数最多只能两个参数？

[echo1937]

JDK的标准库只支持传入两个数字。

[Allen-Scai]

大佬，没太明白空间优化的时候，为什么左上方的dp[i - 1, j - 1]会丢失呢？能详细解释下嘛

[pianfan]

在空间优化中，若为正序遍历行和列，则每次状态转移时，dp[j - 1] 实际上已更新为 dp[i, j - 1]，而非原先的 dp[i - 1, j - 1]

[wzhuo2022]

dp[i-1][j-1]在单行里是dp[j-1]，他已经在循环j-1次更新过了，当前j次循环，只能看到更新后的值

[SSR-chen]

感觉状态的设计最难了，大佬们能分享一下心得吗

[ChineseCz]

个人思路：题目可按决策树分化问题(则可回溯穷举)，则思考优化方案，即原问题可否自顶向下分解，题目是将Str1转化为Str2，可知变量即S1,S2,则原问题Pro[s1,s2]按增删换决策，对应为Pro[s1-1,s2-1],Pro[s1-1,s2],Pro[s1,s2-1];
其实就是先想 暴力搜索的分解思路，再改成自底向上的动规写法，自然就知道状态是什么。

[zhengComing]

图14-30 dp[i-1,j]和dp[i,j-1]的对应的颜色搞错了

[walkerwzy]

状态转移的表格很易懂, 就是它左上的三个格子的最小值, 问题是这个例子比前几个背包问题要抽象, 我不知道竖排bag和横排pack的每个节点里发生了什么, 不知道能不能做个图表示当前交换后变成了什么? 比如pag, ppg, ppp, 我就卡在这一步没法理解.

[walkerwzy]

看了些老外的讲解终于明白了, 其实把横纵轴分别写成"" p pa pac pack , "" b ba bag就好理解了, 比如把A行C列, 其实表示的是"ba"转成"pac"有几种办法.
有些人自动就按这么理解, 就没有障碍, 我是按一个一个字母在转换, 就绕进去了.

[Feitengs]

%%%%%%%%%%%

[KF-14]

图 14-29 把这里的删除看成给t字符串添加一个’k‘应该更便于理解，因为这个问题中字符串s,t是对称的，editDistanceDP(s,t)=editDistanceDP(t,s)。这样处理以后：

• 增加操作将问题变成dp[i+1,j]，由于两个新字符串最后一个元素相同dp[i+1,j]=dp[i,j-1]
• 同理删除操作将问题变成dp[i,j+1]，两个新字符串最后一个元素相同dp[i,j+1]=dp[i-1,j]
• 替换操作直接把字符串最后一个元素变为相同，dp[i,j]=dp[i-1,j+1]

这样处理三种操作都会将最后一个字符变为相等，因此后面状态转移方程为这三种操作中的最小值加上这一步操作

[KF-14]

写错了，替换操作应该是dp[i,j]=dp[i-1,j-1]

[syutengu]

JS版本的暴力解法。

  function minDistance(s, t) {
    return dfs()

    function dfs(i = 0, j = 0) {
      /* 如果s的指针i先越界，则返回t的剩余字符串长度（即为剩余所需编辑次数） */
      if (i === s.length) return t.length - j
      /* 如果t的指针j先越界，则返回s的剩余字符串长度（即为剩余所需编辑次数） */
      if (j === t.length) return s.length - i
      /* 如果两指针所指字符相同（即本轮不为编辑距离的增加作贡献），则各向后移动1，递归执行 */
      if (s[i] === t[j]) return dfs(i + 1, j + 1)
      /* 需要编辑的一般情况： 本轮解 = 取三种可能操作结果之最小值 + 本轮操作1次 */
      return Math.min(
        dfs(i + 1, j), //删除s[i]后，剩余子问题为dp[i+1,j]
        dfs(i, j + 1), //在s[i]后添加t[j]后，剩余子问题为dp[i,j+1]
        dfs(i + 1, j + 1), //将s[i]替换为t[i]，剩余子问题为dp[i+1,j+1]
      ) + 1
    }
  }

[Xi-Row]

想出编辑距离问题的人真是个天才

[gwo-001]

确实……