leetcode/algorithms/fibonacci-number.js at main · w2xi/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 斐波那契数
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  // 0 1 1 2 3 5 8 ...

  // 0. DP
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    const sum = dp[0] + dp[1];
    dp[0] = dp[1];
    dp[1] = sum;
  }
  return dp[1];


  // 1. 递归 + 记忆化
  // const memo = [0, 1];
  // const fibMemo = (n) => {
  //   if (memo[n] != null) {
  //     return memo[n];
  //   }
  //   return (memo[n] = fibMemo(n - 1) + fibMemo(n - 2));
  // };

  // return fibMemo(n);

  // 2. 递归
  // if (n < 1) return 0;
  // if (n <= 2) return 1;

  // return fib(n - 1) + fib(n - 2);

  // 3. 迭代
  // if (n < 1) return 0;
  // if (n <= 2) return 1;
  // let result = 0;
  // let last = 0;
  // let curr = 1;

  // for (let i = 2; i <= n; i++) {
  //   result = last + curr;
  //   last = curr;
  //   curr = result;
  // }
  // return result;
};