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?

這是一道動態(tài)規(guī)劃的題目，每一步的狀態(tài)都與之前一步的狀態(tài)有關(guān)，這道題總結(jié)出的規(guī)律就是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;
};