746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of i^th step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example: 1

Input: cost = [10,15,20]

Output: 15

Example: 2

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Step I (Solving using Recursion):

• The first thing that you should see is that we can move 1 or 2 steps at a time.
• So, if there are N stairs, we can reach the N^th stair from (N-1)^th stair and (N-2)^th stair.
• So, if we calculate minCost to get to (N-1)^th stair and (N-2)^th stair, we can get the minCost to reach the N^th stair (i.e noOfWays(N - 1) + noOfWays(N - 2) = noOfWays(N)).
• Also handle the base case, which is N = 0 or 1, in those cases you will return cost[0] or cost[1] respectively.
• Now you can code this recursively.

Full Code using Recursion (Java): class Solution { public int minCostClimbingStairs(int[] cost) { return recur(cost.length, cost); } int recur(int idx, int[] cost) { // handling cases if idx becomes lesser than 0. if(idx < 0) return Integer.MAX_VALUE / 4; // base case #1 if(idx == 0) return cost[0]; // base case #2 if(idx == 1) return cost[1]; // current cost int curCost = 0; // we will only have stairs from 0 to N - 1 // we won't have cost for N^th stair // so we are checking if we don't have landed on N^th stair or not. if(idx != cost.length) { curCost = cost[idx]; } // returning currentCost + minimum cost from state after taking 1 step and state of taking 2 steps return curCost + Math.min(recur(idx - 1, cost, dp), recur(idx - 2, cost, dp)); } }

Step II (From TLE to Accepted using DP):

• Now if we use recursion, we will be computing many states again and again.
• This will lead to TLE.
• This can be shown by the following example.
• To compute minCost(5), we need to compute minCost(4) and minCost(3).
• To compute minCost(4), we need to compute minCost(3) and minCost(2).
• To compute minCost(3), we need to compute minCost(2) and minCost(1).
• Here we can notice that, minCost(3) and minCost(2) are being computed twice.
• If we had somehow bigger data, this would have resulted into TLE.
• So we will store the results of the subproblems.
• We will take the computed value of minCost(3) and store it in dp[3], and likewise for all 1 to N.
• All above things are explained through code below.
• Always remember, the result to a subproblem is obtained after the recursion from that state returns.

Full Code using DP (Java): class Solution { public int minCostClimbingStairs(int[] cost) { // creating an array to store the result of subproblem. int[] dp = new int[cost.length + 1]; // marking all subproblems as unsolved. Arrays.fill(dp, -1); return minCost(cost.length, cost, dp); } int minCost(int idx, int[] cost, int[] dp) { if(idx < 0) return Integer.MAX_VALUE / 4; if(idx == 0) return cost[0]; if(idx == 1) return cost[1]; // checking if we have solved the subproblem // if yes, return the value // if no, go to minCost(idx - 1), minCost(idx - 2) if(dp[idx] != -1) return dp[idx]; int curCost = 0; if(idx != cost.length) { curCost = cost[idx]; } // storing the result of current subproblem in dp dp[idx] = curCost + Math.min(minCost(idx - 1, cost, dp), minCost(idx - 2, cost, dp)); return dp[idx]; } }