70. Climbing Stairs

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?

这是一道动态规划的题目，每一步的状态都与之前一步的状态有关，这道题总结出的规律就是f(n)=f(n-1)+f(n-2)。这里最直观的想法就是使用递归：

var climbStairs = function(n) {
    if (n===1) {
        return 1;
    } else if (n===2) {
        return 2;
    } else {
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

但是递归里有太多重复的计算，所以会比较慢。那就使用最普通的方法一个一个加：

var climbStairs = function(n) {
    if(n===0||n==1||n==2){
        return n;
    }
    var step1 = 1;
    var step2 = 2;
    var stepn = 0;
    var i = 3;
    while(i<=n){
        stepn = step1 + step2;
        step1 = step2;
        step2 = stepn;
        i++;
    }
    return stepn;
};