Leetcode 746. Min Cost Climbing Stairs

Problem

Leetcode 746 - Min Cost Climbing Stairs

Example:

Input: cost = [10, 15, 20]
Output: 15

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

Approach

We can use dynamic programming to solve this problem. We will use a list to store the minimum cost to reach the i-th step. We will initialize the list with the cost of the 0th and 1st step. Then we will iterate through the list, and for each step, we will add the cost of the current step to the minimum cost to reach the next step.

Visualization of the approach:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
dp[0] = cost[0] = 1
dp[1] = cost[1] = 100

dp[2] = min(dp[0], dp[1]) + cost[2] = min(1, 100) + 1 = 2
dp[3] = min(dp[1], dp[2]) + cost[3] = min(100, 2) + 1 = 2
dp[4] = min(dp[2], dp[3]) + cost[4] = min(2, 2) + 1 = 3
dp[5] = min(dp[3], dp[4]) + cost[5] = min(2, 3) + 100 = 103
dp[6] = min(dp[4], dp[5]) + cost[6] = min(3, 103) + 1 = 4
dp[7] = min(dp[5], dp[6]) + cost[7] = min(103, 4) + 1 = 5
dp[8] = min(dp[6], dp[7]) + cost[8] = min(4, 5) + 100 = 105
dp[9] = min(dp[7], dp[8]) + cost[9] = min(5, 105) + 1 = 6

The answer is the minimum cost to reach the last step, which is dp[9].

Here is the Python code for the solution:

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

        for i in range(2, n + 1):
            dp[i] = min(dp[i - 2], dp[i - 1]) + (cost[i] if i < n else 0)
        
        return dp[n]    

Time Complexity and Space Complexity

Time Complexity: $O(n)$ since we are iterating through the list n times.

Space Complexity: $O(n)$ since we are maintaining a list of size n.