查找斐波納契數(shù)列中第 N 個數(shù)吧碾。
所謂的斐波納契數(shù)列是指：
前2個數(shù)是 0 和 1 。
第 i 個數(shù)是第 i-1 個數(shù)和第i-2 個數(shù)的和。
斐波納契數(shù)列的前10個數(shù)字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
您在真實的面試中是否遇到過這個題？
Yes
樣例
給定 1家乘，返回 0
給定 2，返回 1
給定 10藏澳，返回 34
class Solution{
public:
/**
* @param n: an integer
* @return an integer f(n)
*/
int fibonacci(int n) {
// write your code here
long long result[100];
result[1]=0;
result[2]=1;
for(int i=3;i<=n;i++){
result[i]=result[i-1]+result[i-2];
}
return result[n];
/*
這樣的代價是時間的太慢仁锯，迭代要比遞歸更好
int fibonacci(int n) {
// write your code here
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}
*/
}
};
