一、斐波那契數列
-
題目描述
寫一個函數，輸入n，求斐波那契數列的第n項。其中斐波那契數列的定義如下：
-
思路
顯然，斐波那契數列已經給出了遞推的方程。通常，有了遞推方程後，那麼即可以用分治，也可以用動态規劃。假設，我們要計算f(5)=f(4)+f(3)=f(3)+f(2)+f(3)=…，
顯然在計算f(5)的是否要重複的計算兩次f(3)。是以如果用分治的話，就會有很多重複計算，這時使用動态規劃比較合适。即重下往上，先計算f(2)，再計算f(3)，f(4)，…，f(n)。
-
C++實作
class Solution {
public:
//動态規劃
int Fibonacci(int n) {
//用f記錄f(n-2)的值，用g記錄f(n-1)的值
int f = 0,g = 1;
while(n--){
g += f;//計算下一個f(n-1)
f = g - f;//計算下一個f(n-2)
}
return f;
}
};
二、跳台階
-
題目描述
一隻青蛙一次可以跳上1級台階，也可以跳上2級台階。求該青蛙跳上一個n級的台階總共有多少種跳法？
-
思路
設上n級台階有f(n)中跳法，那麼有f(n)=f(n-1)+f(n-2)。而且f(1)=1,f(2)=2。綜上，有遞推公式
顯然，仍然是斐波那契數列。
-
C++實作
class Solution {
public:
int jumpFloor(int number) {
int f = 1,g = 2;
number--;
while(number--){
g = g+f;
f = g-f;
}
return f;
}
};