知识卡片

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

滚动网格要读左新上旧

理解等级:中级

单行数组可同时保存上一行未更新的上方值与当前行已更新的左方值。按列从左到右计算,dp[j]仍是上方旧值,dp[j-1]已是左方新值,便能形成当前最小路径代价。

每行先单独更新首列,再处理其余列。反向扫描会改变依赖含义,不能仅因为少一维就随意换顺序;若要恢复完整路径,还需额外记录或重算。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      因为数组dp 只能表示一行的状态,所以我们无法提前初始化首列状态,而是在遍历每行时更新它: // === File: min_path_sum.go === 第14 章 动态规划 hello‑algo.com 325 /

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[19226,19336)) - 结论依据:实际minPathSumDPComp初始化/首列与内循环,解释原地覆盖时新旧值。 - 原始内容:因为数组dp 只能表示一行的状态,所以我们无法提前初始化首列状态,而是在遍历每行时更新它: // === File: min_path_sum.go === 第14 章 动态规划 hello‑algo.com 325 /