跳到主要内容

斐波那契题库

一、认识​

斐波那契数列 指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...。这个数列从第3项开始，每一项都等于前两项之和。

1.1 递推公式​

斐波那契公式: F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2)

一、N 位斐波那契数列​

1.1 迭代-双指针​

function getFib(n) {
  let a = 0;
  let b = 1;
  let result = [];
  while (n--) {
    [a, b] = [b, a + b];
    result.push(a);
  }
  return result;
}

const fib = getFib(10);
console.log(fib);

1.2 迭代-三指针​

function getFib(n) {
  let x = 0;
  let y = 0;
  let z = 1;
  let result = [];
  for (let i = 0; i < n; i++) {
    x = y;
    y = z;
    z = x + y;
    result.push(y);
  }
  return result;
}

const fib = getFib(10);
console.log(fib);

1.3 迭代-Generator​

function* fibonacci() {
  let [prev, curr] = [0, 1];
  for (;;) {
    yield curr;
    [prev, curr] = [curr, prev + curr];
  }
}

function getFib(n) {
  const reuslt = [];
  for (let value of fibonacci()) {
    if (reuslt.length >= n) {
      return reuslt;
    }
    reuslt.push(value);
  }
}

const fib = getFib(10);
console.log(fib);

1.4 递归-尾递归优化​

function getFib(n,a=0,b=1,result=[]){
    if(result.length >= n){
        return result;
    }
    result.push(a);
    return getFib(n,b,a+b,result);
}

const fibList = getFib(11);
console.log(fibList);

getFib(n) 的栈帧数的内存复杂度是 O(1)

1.5 递归-缓存递归递归​

function getFib(n) {
  const result = [1, 1];

  const fibonacci = (n) => {
    if (n < 2) {
      return result[n];
    }
    if (result[n] != undefined) {
      return result[n];
    }
    let value = fibonacci(n - 1) + fibonacci(n - 2);
    result[n] = value;
    return value;
  };
  fibonacci(n);
  return result.slice(0, n);
}

const fib = getFib(10);
console.log(fib);

二、斐波那契数列第 N 位​

2.1 迭代-双指针​

function getFibByN(n) {
  let a = 0;
  let b = 1;
  while (n--) {
    [a, b] = [b, a + b];
  }
  return a;
}

const fibN = getFibByN(1);
console.log(fibN);

2.2 迭代-三指针​

function getFibByN(n) {
  let x = 0;
  let y = 0;
  let z = 1;
  for (let i = 0; i < n; i++) {
    x = y;
    y = z;
    z = x + y;
  }
  return y;
}

const fibN = getFibByN(10);
console.log(fibN);

2.3 迭代-Generator​

function* fibonacci() {
  let [prev, curr] = [0, 1];
  for (;;) {
    yield curr;
    [prev, curr] = [curr, prev + curr];
  }
}

function getFibByN(n) {
  let index = 1;
  for (let value of fibonacci()) {
    if (index >= n) {
      return value;
    }
    index++;
  }
}

const fibN = getFibByN(10);
console.log(fibN);

1.4 递归-暴力递归​

function getFibByN(n) {
  if (n < 2) {
    return n;
  }
  return getFibByN(n - 1) + getFibByN(n - 2);
}

const fibN = getFibByN(10);
console.log(fibN);

getFibByN(n) 的栈帧数的内存复杂度是 O(2^n), 当求值 getFibByN(1000) 的时候其实已经无法计算了。

1.5 递归-尾递归优化​

function getFibByN(n,a=0,b=1){
    if(n === 0){
        return a;
    }
    return getFibByN(n-1,b,a+b);
}

const fibN = getFibByN(10);
console.log(fibN);

getFibByN(n) 的栈帧数的内存复杂度是 O(1), 求值 getFibByN(1000) 的时候其实也挺快

1.6 递归-缓存递归优化​

function getFibByN(n) {
  const result = [1, 1];

  const fibonacci = (n) => {
    if (n < 2) {
      return result[n];
    }
    if (result[n] != undefined) {
      return result[n];
    }
    let value = fibonacci(n - 1) + fibonacci(n - 2);
    result[n] = value;
    return value;
  };

  return fibonacci(n - 1);
}

const fibN = getFibByN(1);
console.log(fibN);

三、N 以内的斐波那契数列​

四、最长的斐波那契数列长度​

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

  • n >= 3

  • 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例1:

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例2:

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

4.1 动态规划​

思路:

  1. 状态定义: dp[i][j]：表示以A[i],A[j]结尾的斐波那契数列的最大长度
  • 二维坐标变一维坐标: dp[i][j]=dp[i*len+j]
  1. 状态转移方程:

  • dp[j][k]=max(A[i]+A[j]=A[k]，i<j<k)(dp[i][j]+1) 意思为：以 A[j]、A[k] 结尾的斐波那契式子序列的最大长度 = 满足 A[i] + A[j] = A[k] 条件下，以 A[i]、A[j] 结尾的斐波那契式子序列的最大长度 + 1

  • 二维坐标变一维坐标的常用方法: dp[j*len+k]=dp[i*len+j]+1;

  • 通过 map 记录 A[k] 元素 value-key;

  1. 初始状态: 初始化为2，因为斐波那契序列最短为3

  2. 问题答案: dp 数组元素中的最大值

function lenLongestFibSubseq(nums) {
    const len=nums.length;
    const map=new Map();
    const dp=new Array(len*len).fill(2);
    let result=0;
    for(let k=0;k<len;k++){
        for(let j=0;j<k;j++){
            if(nums[k]-nums[j]<nums[j]&&map.has(nums[k]-nums[j])){
                let i=map.get(nums[k]-nums[j]);
                dp[j*len+k]=dp[i*len+j]+1;
                result=Math.max(result,dp[j*len+k]);
            }
        }
        map.set(nums[k],k);
    } 
    return result>=3?result:0;
};