Start learning free

LESSON 319 OF 338 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in Go: In-Place Dynamic Programming

Practice O(n) Read the full explanation

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top floor, given that you can either start from the step with index 0 or the step with index 1. 

                             ___________
                        ___ | Final Step
                   ___ | 20
             ___ | 15
__________ | 10
First Step

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

  1. cost will have a length in the range [2, 1000].
  2. Every cost[i] will be an integer in the range [0, 999].

STEP 1 OF 3
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in Go, explained

    Problem overview

    The function minCostClimbingStairs(cost) receives a slice where cost[i] is the price of stepping on stair i. Once you have paid for a stair you may climb one or two stairs. You can start on stair 0 or on stair 1, and the goal is the top, one position past the last stair. The function returns the least total you must pay.

    With cost = [10, 15, 20] the answer is 15: start on stair 1, pay 15 and jump two stairs to the top. With cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6. The path steps on the six stairs priced 1 and avoids every 100, taking two-stair jumps over the expensive ones. The notes promise at least 2 stairs, up to 1000, with each price from 0 to 999.

    Approach: the cheapest way to stand on each stair

    Trying all combinations of one-stair and two-stair moves grows exponentially with the number of stairs. A simpler view: the cheapest total to stand on stair i and pay for it depends only on the two stairs just before it. You can only arrive from stair i - 1 or stair i - 2, so

    total(i) = cost[i] + min(total(i-1), total(i-2))

    Stairs 0 and 1 are starting points, so their totals are just their own prices. After computing the totals up to the last stair, the top can be reached from either of the last two stairs, so the answer is the smaller of those two totals.

    The lesson stores the totals in cost itself. Each entry is read for the last time two steps after it is computed, and overwriting it with its total leaves nothing else needing the original price. For the first example, cost becomes [10, 15, 30], and the answer is min(15, 30) = 15. For the second example it becomes:

    [1 100 2 3 3 103 4 5 104 6]

    The last two entries are 104 and 6, so the answer is 6.

    Step by step

    1. Loop from stair 2. Declare i with := and run while i < len(cost). Stairs 0 and 1 need no update.
    2. Accumulate. Add the cheaper of the two previous totals, min(cost[i-1], cost[i-2]), to cost[i].
    3. Return the cheaper end. The top is one past the last stair, reachable from the last or the second-to-last, so return the smaller of those two totals.

    The solution in Go

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

    Go details worth a closer look:

    • The function changes the caller's slice. A slice value is a small header pointing at an array, and passing it copies the header, not the elements. So cost[i] += ... writes into the caller's data. After the call with [10, 15, 20], the caller sees [10 15 30]. If the original prices are needed afterwards, copy the slice first with slices.Clone or append([]int(nil), cost...).
    • Built-in min. Since Go 1.21 it is available for numbers without an import.
    • The compound assignment += evaluates the right side first, which reads the previous two entries, and then updates cost[i] in place.
    • Counting from the end. Go has no negative indices, so the last element is cost[len(cost)-1].
    • The loop has a single bound. len(cost) is re-evaluated each pass, but the slice isn't resized, so it stays constant.

    Edge cases and common mistakes

    • Exactly two stairs. The loop doesn't run, and the answer is the cheaper of the two prices. For [5, 3] that is 3: start on stair 1 and step to the top.
    • All zeros. The answer is 0.
    • Fewer than two stairs. The notes exclude it. With one element cost[len(cost)-2] would index -1 and panic.
    • Returning only cost[len(cost)-1]. That forces the last stair to be stepped on, but a two-stair jump from the second-to-last one can skip it. In the first example, 30 would be the wrong answer.
    • Reading the modified values as prices. After the loop, cost holds totals, not prices, so any later use of the slice must account for that.

    Complexity

    One pass over the slice does constant work per element, so the time is O(n). Since the table is the input slice itself, the extra space is O(1). A version that leaves the input untouched would keep the last two totals in two variables, which also takes O(1) extra space.

    Testing

    Try [10, 15, 20] (answer 15), [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] (answer 6) and [5, 3] (answer 3).

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free