LeetCode 746: Min Cost Climbing Stairs — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Easy — Dynamic Programming | Array

The Problem

Find the minimum cost to reach the top of a staircase where you can climb either 1 or 2 steps at a time, and each step has an associated cost. You can start from either step 0 or step 1.

Approach

Use dynamic programming to build up the minimum cost to reach each step. For each step, calculate the minimum cost by taking the cheaper of the two previous steps plus the current step's cost. Finally, return the minimum of the last two steps since you can reach the top from either.

Time: O(n) · Space: O(n)

Code

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        if n <= 1:
            return 0  # No cost if there are 0 or 1 stairs

        dp = [0] * n  # Initialize a list to store minimum costs

        # Base cases
        dp[0] = cost[0]
        dp[1] = cost[1]

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

        return min(dp[n - 1], dp[n - 2])