Given an integer array cost, where cost[i] represenst the expense required to step onto stair i, you may advance either one or two steps after paying the associated cost. You may begin your ascent from either index 0 or index 1. Compute the minimum total cost to reach the position just beyond the last stair — i.e., index len(cost).

This is a classic dynamic programming problem. Let min_cost[i] denote the minimal expense to reach stair i. Since reaching stair i can only happen from stair i-1 (paying cost[i-1]) or from stair i-2 (paying cost[i-2]), the recurrence relation becomes:

min_cost[i] = min(min_cost[i-1] + cost[i-1], min_cost[i-2] + cost[i-2])

Base cases: no cost is incurred before stepping onto any stair, so min_cost[0] = 0 and min_cost[1] = 0.

Because only the two most recent states are needed, space can be optimized to O(1):

class Solution:
    def minCostClimbingStairs(self, expenses: List[int]) -> int:
        prev2 = 0  # min cost to reach step 0
        prev1 = 0  # min cost to reach step 1
        
        for step in range(2, len(expenses) + 1):
            current = min(prev1 + expenses[step - 1], prev2 + expenses[step - 2])
            prev2, prev1 = prev1, current
        
        return prev1