4 -【经典面试】爬楼梯

[OceanApart]

https://leetcode-cn.com/problems/climbing-stairs/

[Brand0n-Zhang]

var climbStairs = function(n) {
    // 上一轮结果 f(n-1)
    let pre = 0
    // 上上轮结果 f(n-2)
    let pre_pre = 0
    // 本轮结果
    let result = 1
    for (let i = 1; i <= n; ++i) {
        pre_pre = pre;
        pre = result;
        result = pre_pre+pre;
    }
    return result;
};

[minjs1cn]

解题思路：

你要想到达第 n 个台阶，那么你只可能是从 n - 1 个台阶 或者 n - 2 个台阶上来的。 所以，第 n 个台阶的走法 = 第 n - 1 个台阶的走法 + 第 n - 2 个台阶的走法

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

    // n - 2 个台阶的走法
    let a = 1
    // n - 1 个台阶的走法
    let b = 2
    // 临时变量
    let temp
    // 一路相加
    for (let i = 3; i <= n; i++) {
      temp = a
      a = b
      b = temp + b
    }
    return b
};

[OceanApart]

/**
 * @param {number} n
 * @return {number}
 * @description
 * 爬到第 n 阶的方法有是先爬到 n - 1 的方法数加上爬到 n - 2 的方法数
 * f(n) = f(n - 1) + f(n - 2)
 */
var climbStairs = function(n) {
    let a = 1 // n - 2 
    let b = 2 // n - 1
    let c     // n

    if (n < 3) {
        return n
    } else {
        for (let i = 3; i <= n; i++) {
            c = a + b
            a = b
            b = c
        }
    }

    return c
};