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

Posted on

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 
};

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s