斐波那契数

[king-lxt]

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

示例 1：

输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：

输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：

输入：4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

[king-lxt]

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

[king-lxt]

let fib = (function() {
  let memory = []
  return function(n) {
      if(memory[n] !== undefined) {
        return memory[n]
    }
    return memory[n] = (n === 0 || n === 1) ? n : fib(n-1) + fib(n-2)
  }
})()

[king-lxt]

var fib = (function () {
  var memory = {}
  return function(n) {
    if(n==0 || n == 1) {
      return n
    }
    if(memory[n-2] === undefined) {
      memory[n-2] = fib(n-2)
    }
    if(memory[n-1] === undefined) {
      memory[n-1] = fib(n-1)
    }
    return memory[n] = memory[n-1] + memory[n-2]
  }
})()

[king-lxt]

优化后的 

function fib(n, prev=1, next=1) {
    if(n<0){
        return -1;    
    }
    if(n===0){
        return 0;
    }
    if(n===1){
        return 1;
    }
    if(n <= 2) {
        return next
    }
    return fib(n-1, next, prev + next)
}

[king-lxt]

while方法

let fib = function(n) {
    let i = 2
    let res = [0,1,1]
    while(i <= n) {
        res[i] = res[i - 1] + res[i - 2]
        i++
    }
    return res[n]
}

[king-lxt]

for 循环

let fib = function(n) {
    if(n<0){
        return -1;    
    }
    if(n===0){
        return 0;
    }
    if(n===1){
        return 1;
    }
    if(n<=2) {
        return 1
    }
    let sum = 0
    let prev = 1
    let next = 1
    for(let i=3;i<=n;i++) {
        sum = prev + next
        prev = next
        next = sum
    }
    return sum
}