解题思路

本题为简单模拟题，按题给条件进行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)。