Start learning free

LESSON 352 OF 414 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in Scala: 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

    SCALA · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in Scala, explained

    Problem overview

    The method minCostClimbingStairs(cost) receives the price of each step of a staircase. Standing on step i costs cost(i) once you pay it, and from there you may climb one or two steps. You can start on step 0 or step 1, and you want the cheapest way to reach the top, which lies just past the last step. The array has between 2 and 1000 entries, each between 0 and 999.

    For cost = [10, 15, 20] the answer is 15: start on step 1, pay 15, and take two steps to reach the top. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6. Starting on step 0 and stepping only on the cheap steps (indexes 0, 2, 4, 6, 7, 9) skips every 100.

    Approach: the cheapest total for each step

    Define the total for step i as the smallest amount you can have paid after paying for step i itself. You can only arrive at step i from step i - 1 or from step i - 2, so:

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

    Steps 0 and 1 need no calculation, because you can start on either one: their totals are just their own costs. The top is one past the last step, and it can be reached from either of the last two steps without paying anything more, so the answer is the smaller of those two totals.

    The lesson stores the totals in cost itself. Step i reads only the two entries before it, which have already been turned into totals, and then writes its own total over its price. No second array is needed.

    For [10, 15, 20] the array becomes [10, 15, 30] (step 2 is 20 + min(15, 10) = 30), and the answer is min(30, 15) = 15.

    Step by step

    1. Loop over the steps from index 2 to the last one with 2 until cost.length. Indexes 0 and 1 are left alone.
    2. Add the cheaper predecessor to the current entry: cost(i) += math.min(cost(i - 1), cost(i - 2)). After this line, cost(i) holds the cheapest total for standing on step i.
    3. Finish with the smaller of the last two totals, math.min(cost(cost.length - 1), cost(cost.length - 2)), as the method's last expression.

    The solution in Scala

    class Solution {

    def minCostClimbingStairs(cost: Array[Int]): Int = {
        for (i <- 2 until cost.length) {
            cost(i) += math.min(cost(i - 1), cost(i - 2))
        }
        math.min(cost(cost.length - 1), cost(cost.length - 2))
    }
}

    Some Scala details in this code:

    • 2 until cost.length excludes the upper bound, so the last index used is cost.length - 1. With to the loop would read past the end of the array.
    • cost(i) += ... updates an array cell. Scala treats it as cost(i) = cost(i) + ..., and arrays are mutable, so the caller's array changes.
    • Arrays are passed by reference. The method modifies the array it was given. After minCostClimbingStairs(Array(10, 15, 20)) the caller's array holds 10, 15, 30. If the original prices are still needed, pass a copy, for example cost.clone.
    • math.min takes two numbers and returns the smaller one. It is available without an import.
    • The last expression is the result. There is no return: the line with math.min is the method's value.

    Complexity

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

    Space: O(1) extra. The totals overwrite the input, so no new array is made. The price is that the input is destroyed. Keeping the prices and tracking only the last two totals in two variables would also be O(1) and would leave the input intact.

    Edge cases and common mistakes

    • Two steps. The loop doesn't run, and the answer is the cheaper of the two. [5, 5] gives 5.
    • Zero costs. [0, 0, 0, 0] gives 0.
    • Returning the last total only. Returning cost(cost.length - 1) forgets that the top can be reached from the second-to-last step. For [10, 15, 20] that would give 30 and not 15.
    • Adding a cost twice. The totals already include each step's price. Adding cost(i) again in the final line would count the last price twice.
    • A one-element array. The notes promise at least 2 steps. With one element, cost(cost.length - 2) is cost(-1) and throws an ArrayIndexOutOfBoundsException.
    • Calling it twice on the same array. The second call would add totals on top of totals, because the array no longer holds the prices. Pass a fresh array each time.
    • Overflow. The totals are at most 1000 * 999, about a million, so Int is safe.

    Testing

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