动态规划经典：菲波那契函数

[wangjs-jacky]

菲波那契数列定义：

F(0) = 0;
F(1) = 1;
F(n)=F(n - 1)+F(n - 2)

[wangjs-jacky]

递归写法：

const fib = (num) => {
  const cache = [];
  cache[0] = 0;
  cache[1] = 1;

  const dp = (n) => {
    /* n == 0 或者 n == 1, 截止直接返回值即可 */
    if (cache[n] !== undefined) {
      return cache[n];
    }
    cache[n] = dp(n - 1) + dp(n - 2);
    return cache[n]
  }
  return dp(num);
}

console.log(fib(10)); 

[wangjs-jacky]

自底向上写法：

/* 自底向上的写法 */

const fib = (num) => {
  const memo = [];
  memo[0] = 0;
  memo[1] = 1;
  for (let i = 2; i <= num; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[num];
}

console.log(fib(10));