知识卡片

普通读书笔记卡 · 5654.c.3.b.4.a.2

滚动编辑距离先存左上旧值

理解等级:中级

编辑距离每格依赖上、左、左上。按列正序覆盖一行时,dp[j]保留上方旧值,dp[j-1]已有本行左值,另用leftUp保存被覆盖前的左上值。每次更新后,把旧dp[j]交给下一列作leftUp。

必须在覆盖前暂存temp,并在同一列循环中更新leftUp;否则下一列读到错误对角。原书扁平化Go括号把temp作用域打乱,不能原样照抄。时间仍nm,辅助空间降到一行;字节/码点单位问题仍需先明确。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      使用一个变量leftup 来暂存左上方的解 ,从而只需考虑左方和上方的解。 此时的情况与完全背包问题相同,可使用正序遍历。代码如下所示: // === File: edit_distance.go === /* 编辑距离

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;spine 7,归一字符[1026,1136)) - 结论依据:实际editDistanceDPComp temp/leftUp及依赖解释,保留源码排版错误。 - 原始内容:使用一个变量leftup 来暂存左上方的解 ,从而只需考虑左方和上方的解。 此时的情况与完全背包问题相同,可使用正序遍历。代码如下所示: // === File: edit_distance.go === /* 编辑距离