vSPARROW

leetcode : 70. Climbing Stairs a bottom up approach using Dynamic Programming

Posted on June 27, 2020

Dynamic Programming – boils down to solve smaller problems to solve bigger ones. How can I eat a loaf of bread? One slice at a time.

We can solve this with O(n) time and O(1) memory

• O(n) time because we will calculate each step to n
• O(1) time because we are using a limited set of variables. We only care about i-1 and i-2 which will help us get each iteration of i

var climbStairs = function(n) {
    let nMinus2=1
    let nMinus1=1
    for(i=2;i<=n;i++){
        let current = nMinus1 + nMinus2
        nMinus2 = nMinus1
        nMinus1 = current
    }
    return nMinus1 //we return nMinus1 because it holds the value of i === n 
};