Start learning free

LESSON 353 OF 415 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in Swift: Dynamic Programming in Place

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

    SWIFT · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in Swift, explained

    Problem overview

    The method minCostClimbingStairs(_ cost: [Int]) receives the price of each step of a staircase. Paying the price of a step lets you climb one or two steps from it. You may start on step 0 or on step 1, and you want the cheapest way to get to the top, which is one position past the last step.

    For cost = [10, 15, 20] the answer is 15: start on step 1, pay 15 and climb two steps to the top. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6: start on step 0 and stand only on the cheap steps, skipping the 100s. The notes say the list has 2 to 1000 steps and each cost is between 0 and 999.

    Approach: the cheapest total to stand on each step

    You can reach step i only from step i - 1 (one climb) or step i - 2 (two). Define the total for step i as the smallest amount you can have paid by the time you have paid for step i itself. Then

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

    Steps 0 and 1 are allowed starting points, so their totals are just their own costs. The top is reached from the last step or the one before it, so the answer is the smaller of the last two totals.

    Instead of allocating a second array, the solution overwrites cost with the totals. Step i only needs two earlier entries, and they have already been converted. For the first example the list changes like this:

    [10, 15, 20]  becomes  [10, 15, 30]

    Step 2 costs 20 plus the cheaper of 15 and 10, so 30. The answer is min(30, 15), which is 15.

    Step by step

    1. Make a mutable copy. A function parameter is a constant in Swift, so var cost = cost declares a new variable with the same name that hides the parameter. The caller's array is not touched, because arrays are copied when changed.
    2. Loop i over 2..<cost.count, every index from 2 to the last one. Steps 0 and 1 already hold their totals.
    3. Add the cheaper predecessor. cost[i] += min(cost[i - 1], cost[i - 2]) turns the price into a running total.
    4. Return the smaller of the last two totals, cost[cost.count - 1] and cost[cost.count - 2].

    The solution in Swift

    class Solution {

    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var cost = cost
        for i in 2..<cost.count {
            cost[i] += min(cost[i - 1], cost[i - 2])
        }
        return min(cost[cost.count - 1], cost[cost.count - 2])
    }
}

    Swift details worth knowing:

    • Shadowing a parameter. var cost = cost is legal at the top of the method. The new cost hides the parameter in the rest of the body, and the right-hand side still refers to the parameter. This is the usual way to get a mutable local from an argument.
    • Value semantics. The assignment copies the array's value, so changing the local never changes the caller's array. The copy is made lazily when the first write happens.
    • Half-open range. 2..<cost.count excludes cost.count, so the last index used is cost.count - 1. With exactly 2 steps the range 2..<2 is empty and the loop is skipped. A list of fewer than 2 steps would give an invalid range and crash, but the notes promise at least 2.
    • += with min. cost[i] += min(...) reads the two earlier entries first and then adds to cost[i] in place.

    Complexity

    Time: O(n). One pass over the steps, with constant work per step.

    Space: O(n). Writing to the copy makes a second array of the same size. Changing the original input would avoid that, and keeping just the last two totals in variables would give O(1). Copying keeps the caller's data safe.

    Edge cases and common mistakes

    • Two steps. With [5, 3] the loop does not run and the answer is min(3, 5), which is 3: start on the cheaper step and climb two.
    • All zeros. [0, 0, 0, 0] gives 0.
    • Returning cost.last. The top can be reached from either of the last two steps, so the last total alone can be too large. In the first example it is 30, but the answer is 15.
    • Treating the top as a step with its own price. It has none: it is just the position after the last step.
    • Starting the loop at 0 or 1. Index i - 2 would be negative, and Swift stops the program on an out-of-range index.
    • Forgetting the copy. Without var cost = cost, the compiler rejects the assignment to cost[i], because parameters are constants.

    Testing

    • [10, 15, 20] gives 15.
    • [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] gives 6.
    • [5, 3] gives 3.
    • [0, 0, 0, 0] gives 0.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free