Min Cost Climbing Stairs
Min cost to reach the top (past the last step) using 1- or 2-step moves from positions 0 or 1.
2 min read
Problem#
Each step has a cost. Pay the cost to leave that step (1 or 2 steps up). Start at 0 or 1. Min cost to reach past the last step.
Examples#
[10,15,20]→15[1,100,1,1,1,100,1,1,100,1]→6
Constraints#
2 <= n <= 1000.
Approach#
dp[i] = min cost to reach step i. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Roll to two scalars.
Solution#
class Solution {public: int minCostClimbingStairs(vector<int>& cost) { int a = 0, b = 0; for (int i = 2; i <= (int)cost.size(); ++i) { int c = min(b + cost[i - 1], a + cost[i - 2]); a = b; b = c; } return b; }};func minCostClimbingStairs(cost []int) int { a, b := 0, 0 for i := 2; i <= len(cost); i++ { c := b + cost[i-1] if a+cost[i-2] < c { c = a + cost[i-2] } a, b = b, c } return b}from typing import List
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: a = b = 0 for i in range(2, len(cost) + 1): c = min(b + cost[i - 1], a + cost[i - 2]) a, b = b, c return bfunction minCostClimbingStairs(cost) { let a = 0, b = 0; for (let i = 2; i <= cost.length; i++) { const c = Math.min(b + cost[i - 1], a + cost[i - 2]); a = b; b = c; } return b;}class Solution { public int minCostClimbingStairs(int[] cost) { int a = 0, b = 0; for (int i = 2; i <= cost.length; i++) { int c = Math.min(b + cost[i - 1], a + cost[i - 2]); a = b; b = c; } return b; }}function minCostClimbingStairs(cost: number[]): number { let a = 0, b = 0; for (let i = 2; i <= cost.length; i++) { const c = Math.min(b + cost[i - 1], a + cost[i - 2]); a = b; b = c; } return b;}Editorial#
Same Fibonacci-shaped recurrence as Climbing Stairs, weighted by the per-step cost. Two scalars suffice.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#