知识卡片
动态规划避免重复子问题
顺序保存较小斐波那契结果,再计算下一项,避免朴素递归反复计算同样子问题。优势来自复用结果而非“没有递归”这一本身:也可用带记忆的递归。原例map记录全部项为线性存储,若只需最终值可保留前两项;基值、负输入和int溢出仍须约定,n=100的输出不能当任意精度正确结果。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 13.6 并发 TCP 服务器 · 查看原书依据
int if i <= 2 { f = 1 } else { f = fn[i-1] + fn[i-2] } fn[i] = f } return fn[n] }
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》13.6 并发 TCP 服务器,spine266(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/13.6.html)。
- 结论依据:真实循环与map依赖,区分原书算法和可选空间改进。
- 原始内容:int if i <= 2 { f = 1 } else { f = fn[i-1] + fn[i-2] } fn[i] = f } return fn[n] }