- 正在填写
- 被读取
- 答案
用动态规划求斐波那契数
斐波那契数是动态规划最经典的入门例子。朴素递归会一遍又一遍地求同样的项,而有了一张记住每一项的表格,工作量只随 n 线性增长。选择一项,选择自底向上或自顶向下,再一步步查看,每个格子都只填一次。 按“播放”观看表格逐步填满,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。选择要计算的项 n 和方法:自底向上从左边开始填表;自顶向下保留递归,但每次先查表,这时表格下方的一行就是尚未返回的调用组成的栈。“新示例”会换一个 n。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 在“第 n 项”中输入要计算的项 n,并选择自底向上或自顶向下。
- 按“播放”,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。
- 观察每个格子如何读取它前面的两个格子。自顶向下时,表格下方的一行是尚未返回的调用组成的栈。
自底向上与自顶向下
自底向上又称制表法,从 F(0) = 0 和 F(1) = 1 开始,从左到右填表:每个新格子都等于它前面两个格子之和。自顶向下又称记忆化,保留递归定义:要求 F(n),就先求 F(n − 1) 和 F(n − 2)。与朴素递归的区别在于,每次调用都先查表,只有格子还是空的时候才去计算这一项。两种方法都把每个格子只填一次,共用 n − 1 次加法。
朴素递归为什么这么慢
没有表格时,F(n) 调用 F(n − 1) 和 F(n − 2),而这两者又都会调用 F(n − 3),依此类推:这些调用构成一棵树,同样的项在树中反复出现。调用次数是 2·F(n + 1) − 1,增长速度和斐波那契数本身一样快:F(10) 要 177 次,F(20) 要 21,891 次,F(40) 超过 3.31 亿次。像这样的重叠子问题,正是动态规划要解决的。
常见问题
什么是动态规划?
一种解题方法:把问题拆成相互重叠的较小问题,每个较小问题只解一次,并把答案存进表格。斐波那契数是最简单的例子:每一项都由它前面的两项得到。
记忆化和制表法有什么区别?
记忆化保留递归代码,在第一次算出某个答案时把它存起来,之后的调用直接读取。制表法按一定顺序填表,保证每个格子需要的答案都已经算好。两者做的加法完全相同;制表法不需要调用栈,而记忆化只计算真正用到的格子。
求 F(n) 需要多少次加法?
用表格时是 n − 1 次:从 F(2) 到 F(n) 每项一次。每次只会读取最后两项,所以程序也可以只保存两个数,而不保存整张表。
为什么应用只到 n = 40?
F(40) = 102,334,155 仍能轻松显示在屏幕上,而朴素递归求它已经需要 331,160,281 次调用。更大的项增长得很快:F(78) 是 JavaScript 数字能精确表示的最大一项。
会把数据发送到任何地方吗?
不会。所有计算都在你的浏览器中完成,你上次的设置保存在本浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器