动态规划 -70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路

碰到这类题我们可以通过高中学的数学归纳法进行推导，可以先将前面几个结果列举出来

所求项就等于前两项之和，类似于斐波那契数列

代码示例

/**
 * @param {number} n
 * @return {number}
 */
// 可以使用dp数组，但只有两个变量，我们可以直接用变量来表示前两个状态的结果
var climbStairs = function(n) {
    if(n<=1) return n
    const dp = new Array(2)
    let pre=1,cur=2
    for(let i =3 ;i<=n;i++) {
        let sum = pre+cur
        pre = cur
        cur = sum
    }
    return cur
};