Here is one more problem from the domain of dynamic programming and has been asked many times in interviews with little variations . The problem statement is quite simple.
You have a staircase having n steps. Each step has a cost associated with it, you can climb 1 or 2 steps at a time from any step. The only constraint is when you move from a step you have to pay the cost associated with that step.
For example you are at the 5th step of the stairs and the cost associated with the 5th step is 12$. Now by rule you can jump to either 6th step or to 7th step but either of these jumps will cost you 12$. Now your goal is to reach the top of the floor in minimum cost. You will be given an array of n length containing cost associated with n steps.
Solution
To reach a solution for a problem, it is essential to understand the problem first. If you fail to comprehend you might end up with either the wrong solution or no solution at all. Now in this problem a few key points on which you should have a clear understanding.
- Start Point and End Point ( top floor ) are not part of the stairs step and hence they don’t have any cost associated with them.
- You have to pay the cost associated with the step only when you want to move from that step and not when reaching the step.
- You can only move 1 step or 2 steps at a time.
- You will be given an Array cost of n length and cost[i] is the cost of the ith step.
Since you extracted out the key points it is time to start working on the solution. It is better to have a pen paper and design and try out what are the possible approaches for the solution instead of straight forward writing the code.
Our objective is to reach the top of the floor and with minimum cost. Now your total cost to at step depends on from where you are coming and reaching to this step.
Let TotalCost(n) is the total cost to reach the nth step of the stair from the ground then there are only two possibilities, either you are coming from (n-1)th step or from (n-2)th .
If you are coming from (n-1)th step
TotalCost(n) = cost[n-1] + TotalCost(n-1)
If you are coming from (n-2)th step
TotalCost(n) = cost[n-2] + TotalCost(n-2)
The minimum of these two is our answer to reach the nth step with minimum cost.
In our problem you can reach to top of the floor in two ways
From nth step or from (n-1)th step
Minimum total cost to reach from these two steps will be our answer
When n=1 means total cost to reach to first step from ground which will be zero
When n=2 the total cost to reach the second step is zero from ground because you can jump from ground to 2 steps to reach the second step without any cost.
So terminating conditions for recursive are n=1 and n=2
int TotalCost(int n){
if(n==1||n==2)
return 0;
return min((TotalCost(n-1) + cost[n-1]),(TotalCost(n-2)+cost[n-2]));
}
As you can observe calculation of TotalCost(n) depends on Total Cost(n-1) and Total Cost(n-2)
Further TotalCost(n-1) depends on Calculation of TotalCost(n-2) and TotalCost(n-2)
We are calculating TotalCost(n-2) 2 times this is known as overlapping subproblems.
Whenever you have overlapping subproblems you can use memorization to avoid unnecessary computation.
Let’s use memorization to optimize our solution
vector<int> mem(n,-1);
int TotalCost(int n,vector<int>& mem){
if(n==1||n==2)return 0;
if(mem[n]!=-1)return mem[n];
mem[n] = min((TotalCost(n-1)+mem[n-1]),(TotalCost(n-2)+mem[n-2]));
return mem[n];
}
In above code we are using a vector to store the results which may be used in later iterations.
All the elements in the vector are initialized to -1 so that we can keep track of whether calculation for this index has been done or not.
The above code will do our job and it is also quite efficient in comparison to the recursive solution but still there is a lot of scope for optimization.
Even with memorization this code uses recursion which in itself uses O(n) space and it uses extra O(n) memory for storing intermediate results.
Another approach to solve this problem is to go bottom to top rather than top to down, this approach will allow you to further curtail your memory requirements to minimum.
In our problem, on every step we need to have the last two calculations for computation, it is better to keep track of the last two calculations instead of storing all the intermediate results in memory. We can have two variables which can hold the last two results and in every iteration these two variables can be updated to hold the latest two. The below code uses O(n) time complexity and O(1) space.
int TotalCost(n)
{
if(n==1 || n==2 )return 0;
int f1=0;
int f2=0;
for(int i=2;i<n;++i)
{
int f3 = min(f1+cost[i-2],f2+cost[i-1]);
f1=f2;
f2=f3;
}
return f2;
}
