509. 斐波那契數(C++)
- 1 題目描述
- 2 示例描述
- 2.1 示例 1
- 2.2 示例 2
- 2.3 示例 3
- 3 解題提示
- 4 解題思路
- 5 源碼詳解(C++)
1 題目描述
斐波那契數,通常用 F(n) 表示,形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始,後面的每一項數字都是前面兩項數字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
給你 n ,請計算 F(n) 。
2 示例描述
2.1 示例 1
輸入:2
輸出:1
解釋:F(2) = F(1) + F(0) = 1 + 0 = 1
2.2 示例 2
輸入:3
輸出:2
解釋:F(3) = F(2) + F(1) = 1 + 1 = 2
2.3 示例 3
輸入:4
輸出:3
解釋:F(4) = F(3) + F(2) = 2 + 1 = 3
3 解題提示
4 解題思路
5 源碼詳解(C++)
class Solution {
public:
int fib(int n) {
int res = 0 , p = 0 , q = 1 ;
for ( int i = 0 ; i < n ; i ++ )
{
p = q ;
q = res ;
res = p + q ;
}
return res ;
}
};