【題目描述】
斐波那契數(shù)城须，通常用 F(n) 表示质和，形成的序列稱為斐波那契數(shù)列火鼻。該數(shù)列由 0 和 1 開(kāi)始隶垮，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和藻雪。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N，計(jì)算 F(N)狸吞。
【示例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.
【提示】
1勉耀、0 ≤ N ≤ 30
【思路1】
1指煎、使用遞歸
2、遞歸性能很差便斥，但是易于理解
3至壤、時(shí)間復(fù)雜度O(2^n) 指數(shù)級(jí)別
4、空間復(fù)雜度O(1)
C代碼實(shí)現(xiàn)：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
【思路2】
1枢纠、迭代實(shí)現(xiàn)
2像街、時(shí)間復(fù)雜度O(n)
3、空間復(fù)雜度O(1)
C代碼實(shí)現(xiàn)：
int fib(int N) {
if (N < 2) {
return N;
}
int a = 0,b = 1;
for (int i = 1; i<N; i++) {
int temp = a;
a = b;
b += temp;
}
return b;
}
