Command Palette

Search for a command to run...

Hectal
Problem 28.2 · DP Foundations: 1DEasy

Min Cost Climbing Stairs

Pattern1D Dynamic Programming

What it teaches: Switching from counting to minimising: same shape, min instead of +.

Practise it on judges as “Min Cost Climbing Stairs”.

The problem

cost[i] is paid when you step on stair i; from there you climb 1 or 2. You may start at stair 0 or 1. Return the minimum cost to reach the top (just past the last stair).

Example 1

Input: cost = [10, 15, 20]
Output: 15

Constraints

  • 2 ≤ n ≤ 1000

Pattern clues in the wording

  • → Minimum total over step choices

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
cost = [10,15,20]
15
2
cost = [1,100,1,1,1,100,1,1,100,1]
6

From slow to fast

Approaches

1. Rolling minimum · O(n)
1

Rolling minimum

Time O(n) Space O(1)

a = dp[i − 2], b = dp[i − 1], both 0 at the start; compute up to i = n.

Approach 1
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;                  // dp[0], dp[1]
        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;
    }
}

Verdict: Two variables.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Two stairs
  • Cheapest path skips expensive stairs

Mistakes people make

  • Treating the last stair as the top (the top is one past it).

Interview

Follow-up questions

How would you return the stairs you stepped on?