Min Cost Climbing Stairs

Problem statement

cost[i] is what you pay to step on stair i. You may start at stair 0 or stair 1. From stair i you climb one or two stairs after paying. The top is one step past the last index. Return the cheapest way up.

Example:

Input:

cost = [10, 15, 20]

Expected output:

15

Why: start on 15, pay it, jump two stairs to the top. Starting on 10 then stepping through 15 costs 25.

A longer one: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] is 6 — you step on the 1s and skip the 100s.

Practice on LeetCode: Min Cost Climbing Stairs

What we are paying

costS(i) means: step on i, pay cost[i], then take the cheaper of a one-stair or two-stair jump:

costS(i) = cost[i] + min(costS(i+1), costS(i+2))
costS(past the end) = 0

You may begin on 0 or 1 without having climbed there. The answer is min(costS(0), costS(1)).

On [10, 15, 20]:

costS(2) = 20 + min(0, 0) = 20
costS(1) = 15 + min(20, 0) = 15
costS(0) = 10 + min(15, 20) = 25

min(25, 15) = 15.

This is the same “must take this index, then jump” shape as House Robber. House Robber maximizes a take and jumps +2 / +3 so neighbors stay silent. Here you minimize a cost and jump +1 / +2.

Why not try every sequence of jumps

From each stair the tree splits. costS(3) is asked from both 1 and 2. There are only n stairs. Remember each one.

Bottom-up is one pass from the top: dp[i] = cost[i] + min(dp[i+1], dp[i+2]), then min(dp[0], dp[1]). Same recurrence, no call stack. You only need the next two values if you want O(1) extra space.

Golang Solution

memo[i] is the cheapest finish if you step on i. Uncomputed cells are -1 (0 is a legal cost). Past the last stair, pay nothing. Compare starting at 0 and starting at 1.

Time: O(n) — each index is solved once
Space: O(n) — memo, plus O(n) recursion depth

func minCostClimbingStairs(cost []int) int {
    memo := make([]int, len(cost))
    for i := 0; i < len(cost); i++ {
        memo[i] = -1
    }
    return min(costS(cost, 0, memo), costS(cost, 1, memo))
}

func costS(cost []int, i int, memo []int) int {
    if i >= len(cost) {
        return 0
    }
    if memo[i] >= 0 {
        return memo[i]
    }

    memo[i] = cost[i] + min(costS(cost, i+1, memo), costS(cost, i+2, memo))
    return memo[i]
}

Two stairs return min(cost[0], cost[1]): from either start you can jump straight to the top. n is at least 2.