作者：小鹤

[面试题] 斐波那契数列求和优化

2年前 ⋅ 0

题目要求如下：对于如下的斐波那契数列求和公式进行优化，前提是优化后的算法依然要使用递归。

<?php
function fn($n) {
    if ($n == 1 || $n == 2) return 1;

        return fn($n-1) + fn($n-2);
}

首先说有什么，问题就是会重复计算，举个例子：比如 $n = 10 的时候，fn(10) = fn(9) + fn(8), 其中计算 fn(9) 的过程中又要计算 fn(8) （因为 fn(9) = fn(8)+fn(7)）, 进一步展开就是 fn(10) = { fn(8) + fn(7) } + { fn(8) } , 说明这里使用 { } 是为了区分对应的两个部分，由此可见 fn(8) 被计算了两次，如果继续拆分，fn(6) 、fn(5) 这些同样被重复计算了多次。

类似的问题被称为重叠子问题。

如何解决？ 递归中的备忘录：解决重复计算的法宝

简而言之就是将计算出来的中间结果存储起来，进而达到复用计算结果的目的。存储中间结果可以使用两种数据结构，一种是数组，一种是哈希。

<?php
$cache = [0, 1, 1];
function fn($n) {
  global $cache;
    if ($n == 1 || $n == 2) return $cache[$n];
    if (!empty($cache[$n]) return $cache[$n];

    return $cache[$n] = fn($n-1) + fn($n-2);
}

参考资料：