Dynamic Programming: Climb to the top of the staircase with minimum cost
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.
Rules of engagement:
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:
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
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.
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.
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.
