Climb the stairs with minimum cost

Problem Statement:

You are given an array with the cost. Where the cost[i] represents the cost of ith step of the stairs.

If you step on the stair, you will pay the cost and you can either climb one or two steps.

Your task is to climb the stairs with minimum cost to reach the top of the floor.

Example

Input: cost = [10,15,20]
Output: 15

You can step on cost[1] and then reach to the top of the floor.
Hence the cost is 15.

Solution

We can solve this problem by using DP.

TO solve a problem by using DP, we need to check if it satisfy the 2 properties of DP. i.e

1. Overlapping Subproblem
2. Optimal Substructure Property.

Coming to this question we will check if we are able to satisfy the above properties:

1. Overlapping Sub problem:

To reach a step, to reach a step at min_cost(n) we need to calculate the min_cost(n-1) and min_cost(n-2).

Similarly to reach a step at (n-1), we need to calculate min_cost(n-2) and min_cost(n-3).

If you observe, we can calculating min_cost(n-2) twice. Hence it is a overlapping sub problem.

2. Optimal Substructure Property.

This property will check if it is possible to construct an optimal solution from the optimal solutions of its sub problems.

If we have an array [5, 3, 4], to reach min_cost(4), i.e stair #3, we can take stair #1 or stair #2.

As we need to minimize the cost, we take stair #2 and it is an optimal solution.

It means, that the optimal solution of one sub problem, leads to the optimal solution of the whole problem.

Hence we satisfied this property also. Hence we can solve this problem with the help of DP

Now this problem can be solved by using:

1. Recursion
2. Top down approach
3. Bottom up approach

1. Recursion:

First we need to identify the recurrence relation between the sub problems.

min_cost(i) = cost[i] + min(min_cost(i-1), min_cost(i-2))

Here the base cases will be:
min_cost(0) = cost[0]
min_cost(1) = cost[1]

In the program below, I have showed you on how to convert the recurrence relation to recursion.

2. Top down approach

We can optimize the above recursion by using top down approach. i.e add memoization to recursion.

This will reduce the problem from exponential to linear.

For this we will create a DP array and store the value. If there is an sub problem, then we take the stored value, instead of computing again.

3. Bottom up approach

In this approach, we start from the bottom and move towards the problem.
It means we start from the base case then we fill the optimal ways to reach the stairs from 0 to N and return N.

So here we are calculating the all the possible intermediate solutions till we reach N.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

int recursion_helper(vector<int>& cost, int n)
{
    if (n < 0) return 0;
    if (n==0 || n==1) return cost[n];

    return  cost[n] + min(recursion_helper(cost, n-1), recursion_helper(cost, n-2));
} 

int calculate_min_cost_ways_recursion(vector<int>& cost) 
{
  int n = cost.size();

    return min(recursion_helper(cost, n-1), recursion_helper(cost, n-2));
}

int top_down_helper(vector<int>& cost, int n, vector<int> &dp)
{
  if (n < 0) 
    return 0;

  if (n==0 || n==1) 
    return cost[n];

  if (dp[n] != 0) 
    return dp[n];

  dp[n] = cost[n] + min(top_down_helper(cost, n-1, dp), top_down_helper(cost, n-2, dp));
  return dp[n];
} 


int calculate_min_cost_ways_top_down(vector<int>& cost) 
{
    int n = cost.size();

    // create a DP array and initialize it to 0
    vector<int> dp(n+1,0);

      //base case
    dp[0]=cost[0];
    dp[1]=cost[1];

    return min(top_down_helper(cost, n-1, dp), top_down_helper(cost, n-2, dp));

}

int table[46]={0};

int calculate_min_cost_ways_bottom_up(vector<int>& cost) 
{
  int n = cost.size();

  for (int i=0; i<n; i++) {
    if (i<2) table[i] = cost[i];
    else table[i] = cost[i] + min(table[i-1], table[i-2]);
  }

  return min(table[n-1], table[n-2]);

}

int main(int argc, char const *argv[])
{
  vector<int> cost = {5, 3, 4};

  cout<<"The number of ways to climb using recursion "<< calculate_min_cost_ways_recursion(cost)<<endl;
  cout<<"The number of ways to climb using top down "<< calculate_min_cost_ways_top_down(cost)<<endl;
  cout<<"The number of ways to climb using bottom up "<< calculate_min_cost_ways_bottom_up(cost)<<endl;

  return 0;
}

Output:

The number of ways to climb using recursion 3
The number of ways to climb using top down 3
The number of ways to climb using bottom up 3