Start learning free

LESSON 352 OF 414 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in Rust: 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 4
    Ctrl + Enter to check

    RUST · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in Rust, explained

    Problem overview

    The function min_cost_climbing_stairs receives a vector cost where cost[i] is the price of standing on step i. Once you pay a step's cost you can climb one or two steps. You may start on step 0 or on step 1, and you must reach the top, which is one position past the last step. The function returns the smallest total you can pay.

    For cost = [10, 15, 20] the answer is 15: start on step 1, pay 15, and jump two steps to the top. For [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6: start on step 0 and step only on the cells that cost 1, skipping the three 100s, and in the middle jump over one of the 1s.

    Approach: the cheapest way to stand on each step

    Trying every sequence of one-step and two-step moves is exponential. Notice instead that the cheapest way to stand on step i depends only on how you got there, and there are only two ways: from step i - 1 or from step i - 2. So if you know the cheapest total for those two steps, the total for step i is the smaller of them plus cost[i], the price of the step itself.

    Steps 0 and 1 are starting points, so their totals are just their own costs. From step 2 on, apply the rule. The top is reached from step n - 1 or step n - 2, and getting off a step costs nothing more, so the answer is the smaller of the last two totals.

    Take [10, 15, 20]. The totals start as 10, 15. Step 2 adds min(15, 10) = 10 to its cost 20, giving 30. The answer is min(30, 15) = 15.

    Step by step

    1. Make cost mutable. The parameter is owned but not declared mut, so rebind it with let mut cost = cost. Store the length in n. This reuses the same vector as the table of totals, so no extra array is needed.
    2. Loop from step 2. The range 2..n covers every index from 2 to n - 1. Steps 0 and 1 need no update.
    3. Add the cheaper predecessor. For each step, add the smaller of the two previous totals to its own cost with += and min.
    4. Return the smaller of the last two totals. cost[n - 1].min(cost[n - 2]) is the final expression, with no semicolon.

    The solution in Rust

    impl Solution {
    fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let mut cost = cost;
        let n = cost.len();
        for i in 2..n {
            cost[i] += cost[i - 1].min(cost[i - 2]);
        }
        cost[n - 1].min(cost[n - 2])
    }
}

    The Rust details worth knowing:

    • Rebinding to add mut. Parameters are immutable by default. let mut cost = cost; creates a new binding with the same name that is mutable. The vector is moved into it, not copied, so it costs nothing. You could also write mut cost: Vec<i32> in the signature, which does the same thing.
    • The min method. Integers have a.min(b), which returns the smaller of two values. Here it reads as "the cheaper of the two earlier totals".
    • Compound assignment with indexing. cost[i] += cost[i - 1].min(cost[i - 2]); reads two cells and writes a third. This is fine because the integers are copied out of the vector before the write; no reference is held while the vector changes.
    • The range 2..n. It excludes n, so i never goes past the last index. For n = 2 it is empty and the loop body doesn't run.
    • The tail expression. The last line has no semicolon, so its value is returned. With a semicolon, the function would return () and the compiler would report a type mismatch.
    • A usize subtraction. n - 1 and n - 2 are safe because the problem guarantees at least two steps. For a shorter vector, n - 2 would underflow and panic in a debug build.

    Complexity

    Time: O(n). The loop visits each step once and does constant work.

    Space: O(1) extra. The input vector is overwritten with the totals, so no second array is allocated. The cost is that the original prices are lost. If you needed them afterwards, you would clone the vector first, which brings the space back to O(n).

    Edge cases and common mistakes

    • Exactly two steps. [5, 3] gives 3: start on step 1 and step to the top. The loop is empty and the final line takes min(3, 5).
    • Zero costs. A vector of zeros gives 0.
    • Returning cost[n - 1] alone. The top can be reached from the second-to-last step too, so you must take the smaller of the last two totals. For [10, 15, 20] the last total is 30, while the answer is 15.
    • Starting the loop at 0 or 1. That would read cost[i - 2] at a negative index, which underflows a usize and stops the program.
    • Forgetting mut. Without rebinding the vector as mutable, the compiler rejects the += assignment.
    • Thinking the totals are step prices. After the loop each cell holds the cheapest total to stand on that step, not the step's own price.

    Testing

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