Date: 2026-06-06
Time: 17:50
min-cost-climbing-stairs/solution.pyThis file solves LeetCode 746 — Min Cost Climbing Stairs. It computes the minimum cost to reach the top of a staircase where each step has an associated cost and you can climb one or two steps at a time, starting from either step 0 or step 1.
Solution.minCostClimbingStairs(cost: List[int]) -> int — The single method. Takes a cost array (length >= 2) and returns the minimum total cost to reach past the last step.
Space-optimized bottom-up DP. The classic DP formulation for this problem uses an array dp[i] = cost[i] + min(dp[i-1], dp[i-2]), representing the minimum cost to reach step i and pay its toll. This solution compresses that array into two rolling variables:
prev2 tracks dp[i-2]prev1 tracks dp[i-1]After the loop, min(prev1, prev2) gives the answer because you can reach the top (one past the last index) from either of the last two steps.
This is the same rolling-variable idiom used in climbing-stairs/solution.py for the Fibonacci-like stair counting problem — the two are structurally related.
Imports: List from typing — used only for the type annotation.
Imported by: min-cost-climbing-stairs/test_solution.py directly. The long "Imported By" list in the prompt is an artifact of the shared Solution class name across the repo — those test files import their own local solution.py, not this one.
1. Initialize prev2 = cost[0], prev1 = cost[1] — base cases for the first two steps.
2. For each step i from 2 to len(cost) - 1:
prev1 as cost[i] + min(prev1, prev2) — cheapest way to arrive at step i.prev2 to the old prev1 via tuple unpacking.3. Return min(prev1, prev2) — you can step over the top from either of the last two positions.
len(cost) >= 2 is assumed (matches the LeetCode guarantee). No guard for shorter inputs.i, prev1 == dp[i] and prev2 == dp[i-1].0 <= cost[i] <= 999, so min comparisons are well-defined and the result is non-negative.None. The method trusts the caller to provide a valid input per the LeetCode contract. An empty or single-element list would raise an IndexError on the base-case initialization.