[LeetCode] Climbing Sairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思路：这道题是斐波那契数列的延伸。首先用最简单的递归的方法

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

不出意料的超时了。替代递归的方法是用动态规划。

class Solution {
public:
    int climbStairs(int n)  
    {  
        vector<int> res(n+1);  
        res[0] = 1;  
        res[1] = 1;  
        for (int i = 2; i <= n; i++)  
        {  
            res[i] = res[i-1] + res[i-2];  
        }  
        return res[n];  
    }  

};

时间复杂度降低了，接下来降低空间复杂度。用变量代替数组

class Solution {
public:
    int climbStairs(int n)  
    {  
        if (n <= 3) return n;
        int f1 = 2;
        int f2 = 3;
        int f3 = 0;
        for (int i = 4; i <= n; ++i) {
            f3 = f2 + f1;
            f1 = f2;
            f2 = f3;
        }
        
        return f3;
    }  

};

最终的时间复杂度O(n),空间复杂度O(1)