Dynamic Programming: Climb to the top of the staircase with minimum cost

climb to the top of this staircase with minimum penalty
Photo by Roberto Carlos Roman on Unsplash

Frankly speaking, I would rather take the elevator, except when an interviewer forces you to take the stairs.

It isn’t fair that you have to exert so much physical effort. On top of it, you have to remember that every step has an underlying penalty.

Your task is to reach the top of the staircase by incurring a minimum possible penalty. As a coder, your step count starts from zero. Your starting step can be step zero or step one, and you can move one or two-step forward.

Note: You will have at least two steps to take.

Examples:

Input: [20, 10, 30]

Output: As you can start from one, you will incur a penalty of 10 and then jump to the top.

Input: [1, 3, 4, 2, 6]

Output: You can incur a penalty of 1 & 4 or 3 & 2 and either way, with a minimum cost of 5 you can reach the top.

Breaking it down

Say suppose your problem looked like the image below:

Choices to get to the top

You can reach the top of the staircase from step 3 or step 4. Those are your only possible choices.

This seems like an optimization problem while making some choices and solving the problem (reaching the top) would require solving the subproblems: you need to know the best way to reach step 3 and step 4.

This problem reeks of dynamic programming.

Bottom-up approach

Computations at each step (literally)

The cost associated with step 0 and step 1 are straightforward as you can start from either of them. The minimum cost of any other step is calculated with the computation below:

DP[i] = Cost[i] + min(Cost[i-1], Cost[i-2])

Life is about tradeoffs or in words, this means to reach the current step n, it is imperative to decide if it is cheaper to come from step n-1 or step n-2.

Now, if you break the problem into its sub-problems, the only thing you need to worry about is the minimum cost of reaching a step 0, then step 1, then step 2… step n.

Solution

Solving the problem with a DP array of size n where n is the number of steps. The DP[i] holds the minimum cost/penalty to reach the step i.

Using DP array

Here the time complexity is O(n) as we have to iterate over all the steps and space complexity is also O(n) as we have a DP array of size n.

Reducing space complexity

If you check out the source code of the solution above, then you will notice that:

Only dp[i-1] and dp[i-2] are required for each i

If we could use two variables to store these values, then we would not need an array of size n, where n is the number of steps.

Space efficient: Storing only the last two stairs data.

Here, in the above solution, only the step i-1 and step i-2 data is stored and updated at the end of each iteration. This ensures the loop invariant of the last two-step data is maintained.

Also, the space complexity of the solution is now O(1) or constant space.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store