问题：

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

分析：

其实就是斐波那契数列的应用，递推公式为： f(i) = f(i-1) + f(i-2)
可以直观的使用递归，但是时间复杂度与规模n成指数关系，下面介绍动态规划解法。

代码：

int climbStairs(int n) {
        // 开一个长度为 n+1 的数组记录状态，也称‘打表’
        if(n==0){
            return 1;
        }
        else if(n==1){
            return 1;
        }
        int dp[n+1] ;
        dp[0]=dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

事实上，由于i 只和前两项有关,我们还可以省下O(n)的空间复杂度，但时间复杂度并未改变

int climbStairs(int n) {
        // write your code here
        if(n==0){
            return 1;
        }
        else if(n==1){
            return 1;
        }
        int m1=1,m2=1;
        for(int i=2;i<=n;i++){
            m2 = m1+m2;
            m1 = m2-m1;
        }
        return m2;
    }