70. Climbing Stairs

problem description

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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

algorithm thought

说是爬楼梯，其实就是斐波拉契数列。当前值等于前两个的值相加。可以用动态规划解决，用一个一维数组保存所有结果。也可以直接用两个变量保存之前的两个数的值，而不保存所有的结果。

code

//用一个数组保存
class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
            return 1;
        vector<int> res(n+1);
        res[1]=1;res[2]=2;
        for(int i=3;i<=n;++i)
            res[i]=res[i-1]+res[i-2];
        return res[n];
        
    }
};

//用两个变量保存
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        int res=0,first=1,second=2;
        for(int i=3;;++i){
            res=first+second;
            if(i==n)
                return res;
            first=second;
            second=res;
        }
        return res;
    }
};

algorithm analysis

利用动态规划来解决斐波拉契数列问题，时间复杂度O(n)，第二种方法相对于第一种方法减少了线性数组的开销，空间复杂度从O(n)减到了O(1)。