Start learning free

LESSON 327 OF 347 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in C#: Dynamic Programming in O(n)

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

    C# · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in C#, explained

    Problem overview

    A staircase has steps numbered from 0, and cost[i] is the price of stepping on step i. After paying, you may climb one or two steps. You can start on step 0 or step 1, and the goal is the top, which is one position past the last step. MinCostClimbingStairs(int[] cost) returns the cheapest total price to get there.

    For cost = [10, 15, 20] the answer is 15: start on step 1, pay 15, and jump two steps to the top. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6, by stepping only on the cheap steps. The array has between 2 and 1000 entries, each between 0 and 999.

    Approach: cheapest way to stand on each step

    Define the total for a step as the cheapest sum you can pay to stand on it, counting the step's own price. You arrive at step i only from step i - 1 or step i - 2, so

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

    Steps 0 and 1 are starting points, so their totals are just their own prices. The top can be reached from the last step or the one before it, which makes the answer the smaller of the last two totals.

    Trying every route directly would branch twice at each step, which is exponential. The table of totals makes each step cost constant time.

    Step by step

    1. Loop from index 2 up to the end of the array. In C#, the size of an array is its Length property, without parentheses.
    2. Add the cheaper predecessor. Inside the loop, add Math.Min(cost[i - 1], cost[i - 2]) to cost[i]. The lesson reuses the input array itself as the table, so after the loop each entry holds the cheapest total for that step instead of its own price.
    3. Return the smaller of the last two totals, cost[cost.Length - 1] and cost[cost.Length - 2]. Both indexes exist because there are at least two steps.

    The solution in C#

    class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        for (int i = 2; i < cost.Length; i++) {
            cost[i] += Math.Min(cost[i - 1], cost[i - 2]);
        }
        return Math.Min(cost[cost.Length - 1], cost[cost.Length - 2]);
    }
}

    Here is the first example traced. Only index 2 changes: cost[2] = 20 + Math.Min(15, 10) = 30. The final line compares cost[2] = 30 with cost[1] = 15 and returns 15.

    C# details:

    • Arrays are reference types. The method receives a reference to the caller's array, so cost[i] += ... changes the caller's data. That is fine for this lesson, but if you need the original values afterwards, copy the array first or use a separate table.
    • += with Math.Min. The compound assignment reads cost[i], adds the minimum of the two previous totals, and stores the result back in the same element.
    • No overflow worries. At most 1000 steps costing at most 999 each give a total below 1,000,000, far inside the int range.

    Complexity

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

    Space: O(1) extra. The array is reused as the table. If you copy it first to protect the input, the space becomes O(n).

    Edge cases and common mistakes

    • Two steps. The loop never runs. For [5, 3] the answer is 3: start on step 1 and step to the top.
    • Returning the last total only. The top can be reached from step n - 2 too, with a two-step jump, so the last entry alone is wrong. For [10, 15, 20] it gives 30 instead of 15.
    • Starting the loop at 0 or 1. The indexes i - 2 would be negative and throw IndexOutOfRangeException.
    • Looking for a price on the top. Only steps in the array have a cost. The top is just where you finish, so nothing is added for it.
    • Reusing an array you still need. Calling the method twice on the same array gives wrong results the second time, because the first call already overwrote the values.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free