746. Min Cost Climbing Stairs

Easy

Problem:

Given an integer array cost, where cost[i] is the cost of the i-th step on a staircase, find the minimum cost to reach the top. You can start from either index 0 or 1, and from each step, you can climb either one or two steps.

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

Solution:

Memoization

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * len(cost)
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, len(cost)):
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
        return min(dp[-1], dp[-2])

Reference: NeetCode

1. https://www.youtube.com/watch?v=ktmzAZWkEZ0

2. 70. Climbing Stairs

Every single index in the array represents the entire cost taking from the index to reach the end of the array or the top of the array. The return value is going to be the minumum of the first two values in the array.

min(25, 30)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # [10, 15, 20] 0

        cost.append(0)
        for i in range(len(cost)-3, -1, -1):
            cost[i] += min(cost[i+1], cost[i+2])
        
        return min(cost[0], cost[1])