知识卡片

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

滚动状态只保留仍被依赖项

理解等级:中级

当前状态若只依赖固定数量的旧状态,可以在每轮计算后丢弃不再使用的旧答案。楼梯只需前两阶,用两个变量同时滚动便可省去整张一维表。

更新顺序必须先保留计算仍需的旧值;不能覆盖后又读取已经改变的变量。压缩也可能丢掉恢复完整路径所需信息,节省答案计算空间不等于所有输出任务都能同样压缩。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      只需两个变量滚动前进即可。代码如下所示: // === File: climbing_stairs_dp.go === /* 爬楼梯:空间优化后的动态规划 */ func climbingStairsDPComp(n i

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[10712,10822)) - 结论依据:实际climbingStairsDPComp a,b多重赋值及滚动定义,保存依赖窗口含义。 - 原始内容:只需两个变量滚动前进即可。代码如下所示: // === File: climbing_stairs_dp.go === /* 爬楼梯:空间优化后的动态规划 */ func climbingStairsDPComp(n i