题解 | #斐波那契数列# 自己递归

class Solution {
public:
    // 注意要求空间复杂度是O(1) 所以不能用vector来做了
    // 先试试dp
    // 为了降低时间 再试试递归
    int recusion(int n)
    {
        if(n<3)
            return 1;
        else
        {
            return recusion(n-2) + recusion(n-1); // 按共公式递归调用
        }
    }
    
    int Fibonacci(int n) {

        if(n<3)
            return 1;
        // int dp1 = 1;
        // int dp2 = 1;
        // int tmp = 0;
        // for(int i=3; i<=n; ++i)
        // {
        //     tmp = dp1 + dp2; //递推

        //     dp1 = dp2;

        //     dp2 = tmp;
        // }

        // return tmp;

        int ans = recusion(n);

        return ans;


    }
};

• 时间复杂度：O(2^n)，每个递归会调用两个递归，因此呈现2的指数增长
• 空间复杂度：O(n), 递归栈的最大深度

那还是不满足 更低时间复杂度