题目

思路

使用递归会重复计算子问题，考虑动态规划，对重复子问题进行缓存

Code

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 1)
            return n;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
};

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 1)
            return n;
        int pre1 = 1 , pre2 = 0,res = 0;
        for(int i = 2; i <= n; i++)
        {
            res = pre1 + pre2;
            pre2 = pre1;
            pre1 = res;
        }
        return res;
    }
};