知识卡片
滚动编辑距离先存左上旧值
编辑距离每格依赖上、左、左上。按列正序覆盖一行时,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 === /* 编辑距离