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.

Easy
Time O(n) Space O(1)
LeetCode
2 min read
dp

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#

Min Cost Climbing Stairs
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.