Finding Minimum Cost for Climbing the stairs using Dynamic Programming

[3126 views]



In this article, we will cover a famous dynamic programming question, "Finding Minimum Cost for Climbing Stairs".
So Let's Start

Minimum Cost To Reach the Top

We are given a staircase that has some steps.
For stepping on a step, we have to pay some cost. Once we pay the cost for a particular step, we can either take one step or take two steps, our objective is to reach the top.

The catch is that we need to find the minimum cost for reaching the top.
We can either start from the step with index 0 or with step 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest starts on cost[1], pay that cost and go to the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Look at the visualization for a better understanding.

Recursion pattern formed

It is very obvious that we can take one step at a time and reach the top, making a total cost of 10+15+20 = 45
But we can minimize in some way.
We need to make one initial choice.
Should I start with the first stair or the second one?
We are using green color to denote that choice, so we jump onto the first step, we pay 10.
From here on we again have two choices, either take one step or take two steps together... We need to consider these all choice slowly and obtain the total cost of reaching the top.

Now lets go with the second choice, that is taking two-step jump initially! We land on the stair where we need to pay 15.
From here on we again have two choices, either take one step or take two steps together... We need to consider these all choice slowly and obtain the total cost of reaching the top.
Initial takes on the question.
  • So I need to reach the top, and I need to do that in the minimum possible cost

  • I also need to make one initial choice, of making the first step of the starting point

  • If I am at a step, I will have to consider its own cost always

  • Also it is certain, I can either come from one step behind or from a couple of steps behind, those are the only possibilities for me.

So considering a rough idea of the things that we have learned so far, we need to find some sort of relation
that can help us in tying things together.
Consider any point in the staircase. Say we are on the ith step!
Now we could have come to this stair either from the step behind or we can come from 2 steps behind.
Those are the only possibilities.
Also, it is quite obvious that we will have to pay for the floor we are on. Makes sense.

  • Now think of the first initial step of the strategy.

  • Should I start from the first step or take a jump already and then move forward?

  • This is one initial extra choice we really need to make!

So the recursive relation might look like:
minCost(i) = cost[i] + min(minCost(i-1), minCost(i-2))
Notice how we are taking the minimum of the two entities above, that is nothing but a way of making the initial choice!
The base cases are pretty obvious, if we have only stepped to take or we have two to take, then we can directly jump onto them.

Recursive implementation in Python:

def minCostforClimbing(cost): n = len(cost) return min(minCost(cost, n-1), minCost(cost, n-2)) def minCost(cost, n): # TERMINATING CASE if n<0: return 0 # BASE CASES if n==0 or n==1: return cost[n] else: return cost[n] + min(minCost(cost, n-1), minCost(cost, n-2
Also as always there is a way of memorizing the results.
There are lots of computations that we are needlessly repeating.
Notice that if you already know the minimum cost for reaching the 3rd step, then there is no point
of calculating it time and time again.

DP based implementation in Python:

# INTRODUCE A DP ARRAY TO STORE THE RESULTS dp = [] def minCostforClimbing1(cost): n = len(cost) dp = [0]*n return min(minCost(cost, n-1), minCost(cost, n-2)) def minCost1(cost, n): # TERMINATING CASE if n<0: return 0 # BASE CASES if n==0 or n==1: return cost[n] if dp[n] != 0: return dp[n] else: dp[n] = cost[n] + min(minCost(cost, n-1), minCost(cost, n-2)) return dp[n]
        



Facing Programming Errors. Get Answer within 48 hours:





Giving is the Master Key to Success, in all applications of human life.


Comments



Search
For Sponsored Advertisement OR Freelance Programming Article Submission, Contact us at atechdailyweb@gmail.com
Recommended Deals Ends in







Quiz Challenge:
Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags