题解 | #斐波那契数列# 【模拟】详细注释 双超100
斐波那契数列
http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
解题思路
本题为简单模拟题，按题给条件进行n次模拟即可。当然也有打表和公式的O(1)解法。
代码
class Solution {
public:
int fib(int n) {
if(n==0) return 0;//如果n为0，返回0
int a = 1;//f(n-1)
int b = 1;//f(n-2)
int ans = 1;
for(int i = 3; i <= n; i++){
ans = a + b; f(n) = f(n-1) + f(n-2)
a = b;//更新f(n-2)
b = ans;//更新f(n-1)
}
return ans;//返回答案
}
};
复杂度分析
时间复杂度： O(n)。
空间复杂度： O(1)。
叮咚买菜工作强度 246人发布