Skip to Content
算法动态规划

斐波那契数列

以斐波那契数列 为例，讲解动态规划的思想。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列的自上而下，使用递归实现，在假设已经求得上面的值的情况下，可以很容易的求得下面的值，但是这种实现方式会有很多重复计算，比如求 F(5) 的时候，需要先求 F(4) 和 F(3)，但是求 F(4) 的时候，又需要先求 F(3) 和 F(2)，这样就会重复计算 F(3)。这种实现方式我们需要保存已经计算过的值，这样就可以避免重复计算。

function fib(n: number): number {
  const mod = 1000000007;
  // 自上而下，递归
  const memo = new Map();
  function dp(n: number): number {
    // base case
    if (n < 2) {
      return n;
    }
    // 去重
    const memoValue = memo.get(n);
    if (memoValue !== undefined) {
      return memoValue;
    }
    const res = (dp(n - 1) + dp(n - 2)) % mod;
    memo.set(n, res);
    return res;
  }
  return dp(n);
}

因为自上而下是递归，空间复杂度比较高，所以我们可以更进一步使用自下而上使用迭代的方式，从下面的值开始计算，这样还能避免重复计算。

function fib(n: number): number {
  const mod = 1000000007;
  // 自下而上，迭代
  const dp = new Array(n);
  // base case
  dp[0] = 0;
  dp[1] = 1;
  // -------
  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
  }
  return dp[n];
}

上面例子的空间复杂度还能更进一步优化，因为我们只需要保存 dp[i-1] 和 dp[i-2]，所以我们可以只使用两个变量来保存。下面就是我们经常看到的题解了。

function fib(n: number): number {
  const mod = 1000000007;
  // 自下而上，迭代，滚动窗口
  if (n < 2) return n;
  // 分别代表上面的 dp[i-1] 和 dp[i-2]
  let dp1 = 1,
    dp2 = 0;
  for (let i = 2; i <= n; i++) {
    const dp_i = (dp1 + dp2) % mod;
    dp2 = dp1;
    dp1 = dp_i;
  }
  return dp1;
}
Last updated on
搜索树