Day 02 : Fibonacci 斐波那契

相信大家对Fibonacci这个名称应该都不陌生
就直接来看题目的定义吧!

Given n, calculate F(n).

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

fibonacci可以说是认识递回最好的题目

看到题目最直觉的想法如下

if n =1:
    return 0;

if n =2:
    return 1;

else:
    return fib(n-1) + fib(n-2)

直接转换成javascript应该就如下

  function fib(n) {
    if (n === 1) {
      return 0;
    } else if (n === 2) {
      return 1;
    } else {
      return fib(n - 1) + fib(n - 2);
    }
  }

但这种方式我们其实会重复做很多的事

从这张图可以看到
我们在fib(5)呼叫了fib(4)
再计算fib(6)时又会去呼叫fib(4)
当n很大时，重复计算是很耗费时间的！

这时候我们就应该思考
『有办法减少重复做的事？』
如果我们把已经算好的数都存到hashTable这样我们就可以以 O(1) 的时间取得我们要的值

就像是查表一样(有一点Dynamic Programming （DP）的感觉 -> 明天会介绍)
因此，我们可以让时间复杂度降低到 O(n)
而空间复杂度，我们最多储存n个数在我们要查的表中，所以space一样是 O(n)

  function fib(n, table = { 1: 0, 2: 1 }) {
    if (n in table) {
      return table[n];
    } else {
      table[n] = fib(n - 1, table) + fib(n - 2, table);
      return table[n];
    }
  }

既然我们可以降低时间复杂度
我们接着思考
『有没有办法再降低空间复杂度?』

我们真的有需要把所有fib(n)的计算结果都存起来吗？
当我们要算fib(3)其实只需要fib(2)和fib(1)

每一次计算其实都只用前两个的结果
也就是我们只需要去存当下要算的前面两个结果
而用不到的就丢到垃圾桶，对吧？
结论-> 我们可以用一个长度为2的阵列来储存前面两个结果就好！
来看看实际的做法吧！

Time: O(n)，Space: O(1)

var fib = function(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    //迷你库存
    const lastTwo = [1, 1];
    let count = 3;
    while (count <= n) {
    //更新库存
      const nextFib = lastTwo[0] + lastTwo[1];
      lastTwo[0] = lastTwo[1];
      lastTwo[1] = nextFib;
      count++;
    }
    return lastTwo[1];
  };

看完这些方式，也别忘记自己实做看看喔！
唯有自己Coding过才会知道自己的bug在哪边！用看的感觉和做起来差很大！！

明日题目预告:
小时候很常被问到的凑钱问题：Coin Change