當前位置:網站首頁>劍指offer——斐波那契數列

劍指offer——斐波那契數列

2022-01-27 04:18:31 MonsterQy

前言

題目就沒有什麼好介紹的了,主要記錄做法

一、普通遞歸

這個方式很簡單,時間複雜度也很爆炸,直接使用遞歸處理:


var fib = function(n) {
    
if(n==1||n==2)return 1
return (fib(n-1)+fib(n-2)) % 1000000007;
};

二、輔助優化

思路為引入一個輔助table,避免重複計算。

function Fibonacci(n)
{
    
   if(n<1)return 0
   let arr = new Array(n+1).fill(0);
   return helper(arr,n)
}
function helper(arr,n)
{
    
    if(n==1||n==2) return 1
    if(arr[n]!=0) return arr[n]
    arr[n]=helper(arr,n-1)+helper(arr,n-2)
    return arr[n]
}
module.exports = {
    
    Fibonacci : Fibonacci
};

3.動態規劃:

function Fibonacci(n)
{
    
 if(n<1)return 0
 if(n==1||n==2) return 1
 let arr = new Array(n+1).fill(0);
 arr[1]=arr[2]=1
  for(let i=3;i<=n;i++)
      {
    
          arr[i]=arr[i-1]+arr[i-2]
      }
   return arr[n]
}

版權聲明
本文為[MonsterQy]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201270418306429.html

隨機推薦