斐波那契与动态规划
用最直接的方法让计算机求第 40 个斐波那契数,它要调用超过 3.31 亿次。用一张表来求,只需 39 次加法。两者的差别就在于动态规划,而几乎每个人第一次接触动态规划,都是从斐波那契数开始的。
问题
斐波那契数从 0、1 开始,之后的每个数都是它前面两个数之和:0、1、1、2、3、5、8、13、21,依此类推。写成规则就是 F(0) = 0,F(1) = 1,F(n) = F(n − 1) + F(n − 2)。这个规则是递归的,直接把它写成递归程序很容易,但这样的程序其实非常慢。
递归为什么会重复
要求 F(5),程序先求 F(4) 和 F(3)。F(4) 又要求 F(3) 和 F(2),于是 F(3) 被算了两次,F(2) 三次,F(1) 五次。把这些调用画成一棵树,每往下一层调用数几乎翻倍,求 F(n) 总共要调用 2·F(n + 1) − 1 次。这些较小的问题相互重叠:同样的问题一再出现。这正说明动态规划能派上用场。
两种记住答案的方法
记忆化保留递归,但把每个答案写进表格,每次调用在做任何计算之前先查表。制表法自底向上填表:先填 F(0) 和 F(1),再由它们得到 F(2),由 F(2) 和 F(1) 得到 F(3),一直到 F(n)。无论哪种方法,每一项都只算一次,所以求 F(n) 只需 n − 1 次加法,而不是指数级的调用次数。
一个例子
自底向上求 F(7):从 0 和 1 开始。然后 0 + 1 = 1,1 + 1 = 2,1 + 2 = 3,2 + 3 = 5,3 + 5 = 8,5 + 8 = 13,所以六次加法后得到 F(7) = 13。朴素递归要调用 2·F(8) − 1 = 41 次才能得到同样的答案。自顶向下时,最初的调用沿着树的左边一直深入到 F(1);在返回的路上,几乎每隔一次调用就会发现答案已经在表中。
名字的由来
理查德·贝尔曼(Richard Bellman)在 20 世纪 50 年代初于兰德公司(RAND Corporation)工作时,为动态规划取了这个名字。他后来写道,选用“规划”(programming)一词,是取它“计划”的旧义;选用“动态”,是因为它听起来很厉害,又让人难以反对。这种方法本身,即借助问题较小版本的答案来解决问题,如今用在拼写检查、路线规划和 DNA 比对等许多地方。
动手探索
打开应用,按“单步”。自底向上时,橙色格子正在填写,两个蓝色格子是它相加的两项。切换到自顶向下,观察表格下方的调用栈增长到 n,然后随着答案返回而缩短;“加法次数”下方的提示会统计有多少次调用是直接从表中得到答案的。
常见问题
什么是重叠子问题?
解题时需要用到不止一次的较小问题。F(n) 和 F(n − 1) 都需要 F(n − 2),所以朴素递归会把它算两次,越往下浪费越成倍增加。动态规划把每个子问题只解一次,并记住答案。
记忆化比制表法快吗?
两者做的加法相同。制表法通常稍快一些,因为它没有函数调用,也不会出现栈空间耗尽;记忆化适合只需要部分较小答案的情况,因为它只计算那些答案。
斐波那契数还能算得更快吗?
能。利用 F(2k) = F(k)·(2·F(k + 1) − F(k)) 和 F(2k + 1) = F(k)² + F(k + 1)²,快速倍增法只需大约 log₂ n 步。使用黄金比例的比内公式(Binet's formula)也能得到同样的数,但由于舍入误差,n 较大时并不可靠。
表格需要多少内存?
完整的表格要存 n + 1 个数,但每个新项只需要它前面的两项,所以只保存两个数的循环就能用常数内存完成同样的工作。如果你需要所有的项,或者想看清这种方法如何运作,保存整张表就很有用。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试用动态规划求斐波那契数