Coding Interview Prep: Climbing Stairs to reach the top (Dynamic Programming)

Solution using Dynamic Programming

/*
Solution using Dynamic Programming
Time Complexity: O(n), n is the number of steps to reach to the top
Space Complexity: O(n) for the dp variable
*/
var climbStairs = function(n) {
    const dp = new Array(n+1).fill(0);

    dp[0] = 1;
    dp[1] = 1;

    for (let i=2; i<=n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n]
};

Dynamic Programming is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.

Explanation

This problem uses Dynamic Programming. We store the values into an array so we don’t have to solve the the subproblems over and over again. We store the value of the previous two steps from the current ith position into an array. This is like the fibonacci number approach.

The brute force way of solving this question is to recursively call the following.

climbStairs(n-1)+climbStairs(n-2)

However, the issue here is that this is a very expensive method to call repeatedly. That’s when dynamic programming comes in handy. Since we would have already have the result climbStairs function for the previous number of steps. We can store those values and do not have to call over and over again anymore.