70. 爬楼梯

[qulingyuan]

70. 爬楼梯

解题思路

爬到第 n 阶可以在第 n-1阶爬1个台阶，或者在n-2阶爬2个台阶。

F(n) = F(n-1) + F(n-2)

解题步骤

定义子问题：F(n) = F(n-1) + F(n-2)。

反复执行：从2循环到n，执行上述公式。

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 2) return 1;
    const dp = [1,1];
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};

可以不用数组，只用两个变量记录即可。可优化时间复杂度为O(1):

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 2) return 1;
    let dp0 = 1;
    let dp1 = 1;
    for(let i = 2; i <= n; i++){
        const temp = dp0;
        dp0 = dp1;
        dp1 = dp1 + temp;
    }
    return dp1;
};