LeetCode 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?

翻譯

你正在爬一個階梯。到頂端總共需走n階。

每次你都可以選擇爬1階或2階，問有幾種不同的方法可以爬到階梯頂端

思路

1. n = 1， result = 1
2. n = 2, result = 1+1 (爬1階兩次 + 一次爬兩階)
3. n = 3, result = 1+2 (前面兩個case相加)
4. n = 4, result = 3+2 (前面兩個case相加)
5. 發現其實這題就是算費氏數列

解題

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n<=1){
        return 1;
    }

    var prev = 1;
    var cur  = 1;
    // 費氏數列 f(n) = f(n-1) + f(n-2)
    for(var i = 2 ; i <=n ; i++){
        var temp = cur;
        cur = cur + prev;
        prev = temp;
    }
    return cur;
};