1. Min Cost Climbing Stairs (LeetCode)
Model answer
The task
Find the minimum total cost to reach the position just beyond the last stair. You may begin at either of the first two stairs, and each move advances one or two stairs.
Key idea
Let dp[i] be the minimum cost to reach position i, where position n is the top beyond the stairs. The last move to i comes from i - 1 or i - 2, so only the two previous DP values are needed.
Approach
- Treat positions
0and1as starting positions with no cost paid yet. - For each position from
2throughn, consider arriving from one or two positions back. - Add the cost of the stair departed from to each candidate.
- Keep only the two most recent DP values.
- Return the minimum cost to reach position
n.
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# Minimum costs to reach positions 0 and 1.
two_back = 0
one_back = 0
# Position n is the top, beyond the final stair.
for position in range(2, len(cost) + 1):
current = min(
two_back + cost[position - 2],
one_back + cost[position - 1],
)
two_back, one_back = one_back, current
return one_back
Complexity:
- Time: O(n), with one pass through the stairs.
- Space: O(1), using only two rolling DP values.
Common follow-ups
- How would you return the actual route? Store each position’s chosen predecessor, then backtrack from the top.
- What if you can climb up to
kstairs at a time? Take the minimum over the previouskreachable positions. - What if the cost depends on the move rather than the stair? Add the corresponding move cost in each transition.