劍指 Offer 10- I. 斐波那契數列

題目

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)）。斐波那契數列的定義如下：

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契數列由 0 和 1 開始，之後的斐波那契數就是由之前的兩數相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請傳回 1。

示例1：

輸入：n = 2

輸出：1

遞歸法：

python版本

class Solution(object):
	def fib(self,n):
		a,b=0,1
		for _ in range(n):
			a,b=b,a+b
		return a%1000000007
           

C++版本：

此時如果你這樣寫法就逾時了

class Solution {
public:
    int a=0;
    int b=1;
    int sum=0;
    int fib(int n) {
        if(n==1) return 1;
        if(n==0) return 0;
        else{
            return (fib(n-1)+fib(n-2))% 1000000007;;
        }
    }
   
};
           

中間存在很多次計算，比如fib（3）,他需要fib(2)和fib(1)，fib(4)需要fib(3)和fib(2)，因而在計算過程中，每一次fib(2),fib(3)都需要重複不斷的計算，浪費了大量的時間，是以我們需要減少這樣的重複計算，因而利用一個哈希表，把計算過的fib(n)的值存在哈希表中，這樣就可以減少大量運算

class Solution{
public：
	unordered_map<int,int> result;
	int dfs(int n){
		if(n==1) return 1;
		else if(n==0) return 0;
		else if(result.count(n)) return result[n]; //判斷如果已經算過，直接傳回,即如果第n個鍵值已經在哈希表出現，說明已經算過
		int a=dfs(n-1)% 1000000007;
		result[n-1]=a;
		int b=dfs(n-2)% 1000000007;
		result[n-2]=b;
		result[n]=(a+b)% 1000000007;
		return result[n];
	}
	int fib(int n){
		return dfs(n);
}
}
           

或者

class Solution{
public:
	int fib(int n){
		vector<int>dp;
		for(int i=0;i<=n;++i){
			if(i==0) dp.push_back(0);
			else if(i==1) dp.push_back(1);
			else {
				dp.push_back((dp[n-1]+dp[n-2])%1000000007);
			}
		}
		return dp[n];
}
};