【算法-动态规划-简单】爬楼梯

[AwesomeDevin]

https://leetcode.cn/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

缓存递归

时间复杂度 O(n)
空间复杂度O(n)

var climbStairs = function(n) {

    const cache = {}
    const fn = (n) => {
        if(n === 1) return 1
        if(n === 2) return 2
        if(cache[n]) return cache[n]
        const res = fn(n-1) + fn(n-2) 
        cache[n] = res
        return res
    }
    return fn
}();

动态规划(滚动数组)

时间复杂度 O(n)
空间复杂度O(1)

var climbStairs = function(n) {
    let a = 0 
    let b = 0
    let c = 1
    for(let i =0;i <n; i++ ){
        b = a
        a = c
        c = a + b
    }
    return c
};

动态规划