Min Cost Climbing Stairs

My approach:

Note: This question is similar to the Climbing Stairs problem with only a little change in conditions so please attempt that question first to understand this.

We can observe a recurrence relation that exists and we can easily solve it by using recursion. On observation, we can see there are overlapping subproblems. To solve that we will use memoization.

Instead of using the top-down approach, we can also solve it using the bottom-up approach by simply using one loop.

My solution:

• Recursive

• Iterative

Code

• Recursion with Memoization

class Solution {
public:

    int helper(vector<int>& cost, int i, int n, vector<int>& dp){

        if(i>n){
            return 1e8;
        }

        if(dp[i]!=-1){
            return dp[i];
        }

        if(i==n){
            return 0;
        }

        if(i==n-1){
            return cost[i];
        }

        int one = helper(cost,i+1,n,dp);
        int two = helper(cost,i+2,n,dp);

        dp[i] = min(one,two)+cost[i];
        return min(one,two)+cost[i];
    }

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

        vector<int> dp(n+1,-1);

        int index0 = helper(cost,0,n,dp);
        int index1 = helper(cost,1,n,dp);

        return min(index0,index1);
    }

};

• Dynamic Programming

class Solution {
public:

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

        vector<int> dp(n+1);

        dp[0] = cost[0];

        dp[1] = cost[1];

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

        }

        return dp[n];
    }
};

Question Link:

https://leetcode.com/problems/min-cost-climbing-stairs/