Start learning free

LESSON 328 OF 348 · DYNAMIC PROGRAMMING

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

    KOTLIN · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in Kotlin, explained

    Problem overview

    The function minCostClimbingStairs(cost) receives an IntArray where cost[i] is the price of stepping on stair i. After paying a stair's cost you may climb one or two stairs. You can start on stair 0 or on stair 1, and the goal is the top, which is one position past the last stair. The function returns the minimum total cost to get there.

    For cost = [10, 15, 20] the answer is 15: start on stair 1, pay 15, and jump two stairs to the top. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6: stand only on the cheap stairs, using steps of two over each 100 and skipping the 1 at index 3. The statement says the array has between 2 and 1000 entries, each between 0 and 999.

    Approach: cheapest total to stand on each stair

    You can reach stair i only from stair i - 1 or stair i - 2, so the cheapest way to stand on it is the cheaper of those two totals, plus the stair's own cost. Stairs 0 and 1 are starting points, so their totals are just their own costs. From there every other total follows from the two before it.

    The top is not a stair. It can be reached from the last stair (one step) or the second-to-last (two steps), so the final answer is the cheaper of those two totals. Standing on the last stair is not required: stepping from the second-to-last directly to the top skips paying for the last one.

    This lesson stores the totals in cost itself. When the loop reaches stair i, the entries before it already hold totals, so the update cost[i] += minOf(cost[i - 1], cost[i - 2]) turns the stair's price into its total. That avoids a second array.

    Step by step

    1. Loop i from 2 until cost.size. Stairs 0 and 1 need no update, because you may start on either of them.
    2. Add the cheaper previous total. cost[i] grows by minOf(cost[i - 1], cost[i - 2]), and afterwards it holds the cheapest total to stand on stair i having paid for it.
    3. Return the cheaper of the last two totals, cost[cost.size - 1] and cost[cost.size - 2], since the top is reachable from either.

    The solution in Kotlin

    class Solution {

    fun minCostClimbingStairs(cost: IntArray): Int {
        for (i in 2 until cost.size) {
            cost[i] += minOf(cost[i - 1], cost[i - 2])
        }
        return minOf(cost[cost.size - 1], cost[cost.size - 2])
    }
}

    The Kotlin details worth a closer look:

    • Arrays are passed by reference. The function receives the caller's IntArray, not a copy, so cost[i] += ... changes the caller's array. After minCostClimbingStairs(intArrayOf(10, 15, 20)) on a variable c, c holds [10, 15, 30]. If the caller still needs the original prices, pass cost.copyOf() or use a separate table.
    • Parameters can't be reassigned, but elements can. A Kotlin function parameter is read-only, so cost = ... would not compile, yet cost[i] = ... is fine because it changes the array's contents, not which array cost names.
    • until. 2 until cost.size stops at the last valid index. 2..cost.size would run once more and throw ArrayIndexOutOfBoundsException.
    • minOf. It is the standard-library function that returns the smaller of its arguments.
    • Compound assignment on elements. cost[i] += x reads the element, adds x and stores the result back.

    Complexity

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

    Space: O(1) extra. The totals are written into the input array. If you keep the input intact with a copy, the space becomes O(n). Two variables holding the previous two totals would also do it in O(1) without changing the input.

    Edge cases and common mistakes

    • Two stairs. [5, 5] returns 5. The loop doesn't run, and the answer is the cheaper of the two starting stairs.
    • Zero costs. [0, 0, 0, 0] returns 0.
    • Returning the last total only. For [10, 15, 20] the last total is 30, but the answer is 15. The top can be reached from the second-to-last stair.
    • Looping from 0 or 1. That reads cost[-1] and throws an exception.
    • Calling the function twice on the same array. The first call overwrites the costs with totals, so the second call starts from the wrong values.
    • Adding the wrong neighbour. Using maxOf instead of minOf finds the most expensive route.

    Testing

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