Day 7: Min Cost Climbing Stairs

Problem Link:

Explore - LeetCode

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.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: Cheapest is: start on cost[1], pay that cost, and go to the top.

Example 2:

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

My Solution:

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i+1], cost[i+2])
        return min(cost[0], cost[1])

Explanation:

This is top-down dynamic programming (DP) approach solution. We can think of this as the build-up of a number of smaller subproblems, starting at the end.

At each step, we can consider the answer to be the combined cost of the current step, plus the lesser result of the total cost of each of the solutions starting at the next two steps. This means that by thinking backward, we can solve the smallest problem first, and then build down from there.

For the last two steps, the answer is clearly their individual cost. For the third to last step, it’s that step’s cost, plus the lower of the last two steps. Now that we know that, we can store that data for later use at lower steps. Normally, this would call for a DP array, but in this case, we could simply store the values in place.

(Note: If we choose to not modify the input, we could create a DP array to store this information at the expense of O(N) extra space.)

So we should iterate downward from the end, starting at the third step from the end, and update the values in cost[i] with the best total cost from cost[i] to the end. Then, once we reach the bottom of the steps, we can choose the best result of cost[0] and cost[1] and return our answer.

• Time Complexity: O(N) where N is the length of cost
• Space Complexity: O(1) or O(N) if we use a separate DP array

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!