Min Cost Climbing Stairs

EASY✓ CHIP-TIMEDLC #746 — FULL STATEMENT ↗

The drill: A staircase where each step charges a fee to land on it, and every stride covers one or two steps. Starting from step 0 or step 1, find the cheapest way to climb past the top.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A staircase charges a fee to land on each of its steps, and every stride covers either one step or two. The climb is allowed to begin standing on step 0 or step 1, free of charge either way.

The climb finishes the moment a stride lands past the very last step — the top itself carries no fee, only a way to get past it.

The task is to find the cheapest total of landing fees paid across any valid sequence of strides that clears the staircase.

EX 01

cost = [5, 5]

→ 5

MINIMUM SIZE, TIE BETWEEN THE TWO STARTS

EX 02

cost = [1, 2, 3, 4]

→ 4

STRICTLY INCREASING FEES

EX 03

cost = [0, 0, 0, 0]

→ 0

EVERY STEP IS FREE

step count is modest, generally under a thousand
each fee is a non-negative integer
climb may start on step 0 or step 1 at no cost
climb ends once a stride clears the final step

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Trying every combination of one-step and two-step strides doubles the branching at each stair — what does a stair need to know about the stairs before it, not the ones after?

HINT 2 THE STRUCTURE

The cheapest way to stand on stair i only depends on the cheapest way to have reached stair i-1 or stair i-2, plus this stair's own fee. That's a recurrence, not a search.

HINT 3 ONE STEP FROM THE ANSWER

Build the cheapest-cost-to-reach array left to right: dp[i] = cost[i] + min(dp[i-1], dp[i-2]), with dp[0] = dp[1] = 0 as free starting points. The answer sits one step past the last stair.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ROLLING CLIMBPATTERN · ROLLING 1-D DPcost = [10, 1, 1, 10]

CHEAPEST COST TO REACH

reach 0 → 0

reach 1 → 0

STEP 1

Climbing can start free at stair 0 or stair 1 — both cost nothing to stand on.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/min-cost-climbing-stairs.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev2, prev1 = 0, 0                     # cheapest cost to reach stair 0, stair 1
        for i in range(2, n + 1):
            prev2, prev1 = prev1, min(prev1 + cost[i - 1], prev2 + cost[i - 2])
        return prev1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 7 LN

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)

        def climb(i: int) -> int:              # branch: take one stair or two
            if i >= n:
                return 0
            return cost[i] + min(climb(i + 1), climb(i + 2))

        return min(climb(0), climb(1))          # start from either free landing

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = 0, prev1 = 0;
        for (int i = 2; i <= n; i++) {
            int cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 12 LN

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return Math.min(climb(cost, 0), climb(cost, 1));
    }

    private int climb(int[] cost, int i) {
        if (i >= cost.length) {
            return 0;
        }
        return cost[i] + Math.min(climb(cost, i + 1), climb(cost, i + 2));
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED