TAGS: Algorithms, Arrays, Dynamic Programming

Imagine you’re about to embark on a journey, a journey up a flight of stairs. But these aren’t your average stairs. Each step comes with a price tag, and you have to pay to proceed. You can choose to climb one or two steps at a time, starting from either the first or second step. The challenge here is to reach the top of the stairs while keeping your wallet as full as possible.

Sounds like a fun game, right? But how do we solve it?

At first glance, you might think of using recursion. Let’s say there are n steps, and the cost of each step is stored in an array cost. You could choose to climb one step, costing cost[0], and then solve the sub-problem of climbing the remaining n-1 steps. Or, you could climb two steps, costing cost[1], and then solve the sub-problem of climbing the remaining n-2 steps. You would then choose the cheaper of these two options.

Here’s a JavaScript function that implements this approach:

var minCostClimbingStairs = function(cost) {
    if(cost.length===0) return 0;
    if(cost.length===1) return 0;
    if(cost.length===2) return Math.min(cost[0],cost[1]);
    return Math.min(cost[0]+minCostClimbingStairs(cost.slice(1)),cost[1]+minCostClimbingStairs(cost.slice(2)))
};

Let’s test the time it takes:

console.time()
console.log(minCostClimbingStairs([841,462,566,398,243,248,238,650,989,576,361,126,334,729,446,897,953,38,195,679,65,707,196,705,569,275,259,872,630,965,978,109,56,523,851,887,91,544,598,963,305]))
console.timeEnd()

Result: 23.631s Clearly, this is not efficient.

The problem with this approach is that there are multiple ways to reach each step, especially as you go further up the stairs. For each possible path, we’re recalculating the minimum cost to reach the top from that step, resulting in a lot of redundant computation.

So, why not calculate the minimum cost to reach the top from each step in advance?

Since the minimum cost to reach a particular step depends on the costs of the steps that follow it, it makes sense to calculate these costs in reverse order, starting from the top of the stairs.

Here’s the revised JavaScript function that uses dynamic programming:

var minCostClimbingStairs = function(cost) {
    cost=[0,...cost] // The cost to reach the current step is 0
    const mins = new Array(cost.length); // Array to store the minimum cost after reach each step
    mins[mins.length-1] = 0;
    mins[mins.length-2] = 0;
    for(var i=mins.length-3;i>=0;i--){ // Start from the third step from the top
        let cost1 = cost[i+1]+mins[i+1]; // Minimum cost if you choose to climb 1 step
        let cost2 = cost[i+2]+mins[i+2]; // Minimum cost if you choose to climb 2 steps
        mins[i] = Math.min(cost1,cost2);
    }
    return mins[0]
};

Let’s test the time it takes:

console.time()
console.log(minCostClimbingStairs([841,462,566,398,243,248,238,650,989,576,361,126,334,729,446,897,953,38,195,679,65,707,196,705,569,275,259,872,630,965,978,109,56,523,851,887,91,544,598,963,305]))
console.timeEnd()

Result: 0.368ms

With this dynamic programming approach, we’ve turned a potentially time-consuming problem into a much more manageable one. Now, you’re ready to conquer any staircase, no matter how costly its steps may be!