Min Cost Climbing Stairs

Difficulty: Easy Link: Day 8: June Leetcode Challenge

Problem Statement

You are given an integer array cost where cost[i] is the cost of ith 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.

Examples

Input: cost = [10,15,20]
Output: 15
Explanation: Cheapest is: start 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].

Constraints

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

Solution

We can move either 1 step or 2 step, this is a choice we have to make in order to minimise the effort for reaching the destination. If you carefully look at the examples, you need to always consider the best of past two choices you made at any point. To reach at any point, we would have either jumped 1 step from previous stair or jumped 2 stairs from last 2 rows. We have to always choose the minimum of the costs. Does it look familiar? Which approach does it screams of?

Dynamic Programming

Congratulations if you guessed it just by reading the problem. If you are new to the Dynamic Programming, then probably this is the starer problem you would see on the Leetcode. To solve any DP problem, there are basically two ways to build up the solution. 1. We can start from the lowest sub-problem and reach the final solution by caching the solved results(Tabulation / Bottom Up Approach). 2. We can start from the main problem and recursively break down in two smaller sub problems and saving those small results along the way to avoid re-computation.

Swift

class Solution {
func minCostClimbingStairs(_ cost: [Int]) -> Int {
var dp = [Int](repeating:0, count: cost.count+1)
for i in 2..<dp.count{
let oneStepCost = dp[i 1] + cost[i 1]
let twoStepCost = dp[i 2] + cost[i 2]
dp[i] = min(oneStepCost, twoStepCost)
}
return dp[cost.count]
}
}

Python

class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# The array's length should be 1 longer than the length of cost
# This is because we can treat the "top floor" as a step to reach
minimum_cost = [0] * (len(cost) + 1)
# Start iteration from step 2, since the minimum cost of reaching
# step 0 and step 1 is 0
for i in range(2, len(cost) + 1):
take_one_step = minimum_cost[i 1] + cost[i 1]
take_two_steps = minimum_cost[i 2] + cost[i 2]
minimum_cost[i] = min(take_one_step, take_two_steps)
# The final element in minimum_cost refers to the top floor
return minimum_cost[1]

Java

class Solution {
public int minCostClimbingStairs(int[] cost) {
// The array's length should be 1 longer than the length of cost
// This is because we can treat the "top floor" as a step to reach
int minimumCost[] = new int[cost.length + 1];
// Start iteration from step 2, since the minimum cost of reaching
// step 0 and step 1 is 0
for (int i = 2; i < minimumCost.length; i++) {
int takeOneStep = minimumCost[i 1] + cost[i 1];
int takeTwoSteps = minimumCost[i 2] + cost[i 2];
minimumCost[i] = Math.min(takeOneStep, takeTwoSteps);
}
// The final element in minimumCost refers to the top floor
return minimumCost[minimumCost.length 1];
}
}

Complexity Analysis

We are iterating over the input linearly for building our memoization table. So, both time and space would be bounded by linear

  • Time complexity: O(N)
  • Space complexity: O(N)

Leave a Reply

Your email address will not be published. Required fields are marked *