LeetCode Problem 746

Difficulty: 🟢 Easy
Topics: Array, Dynamic Programming

Solution

LeetCode 746 - Min Cost Climbing Stairs

Problem Understanding

This problem gives us an array named cost, where each element represents the cost of stepping onto a particular stair. If cost[i] equals 10, that means stepping on stair i requires paying 10.

From any stair, we are allowed to move either one step or two steps upward. The goal is to reach the "top" of the staircase while spending the minimum possible amount of money.

An important detail is that the top is not an actual index in the array. If the array has length n, then the top is considered to be just beyond index n - 1. You can reach the top either from the final stair or from the second-to-last stair.

Another key detail is that we may start from index 0 or index 1. This means we do not necessarily have to pay the first stair's cost. We are free to choose the cheaper starting strategy.

For example, with:

cost = [10, 15, 20]

we can either:

• Start at index 0, pay 10, then move to index 2, pay 20, total 30
• Start at index 1, pay 15, then jump directly to the top, total 15

The minimum cost is therefore 15.

The constraints are relatively small:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

An array length of 1000 is small enough for dynamic programming solutions, but large enough that exponential brute force recursion would become too slow.

Several edge cases are important to recognize early:

• The array may contain only two elements, which is the smallest valid input.
• Costs can be zero, meaning some stairs are effectively free.
• The cheapest path may skip expensive stairs using two-step jumps.
• A greedy strategy that always picks the cheaper immediate step does not always work globally.

This problem is fundamentally about making optimal decisions while reusing solutions to overlapping subproblems, which is a classic indicator of dynamic programming.

Approaches

Brute Force Approach

The brute force solution tries every possible path from the starting position to the top.

At each stair, we have two choices:

1. Move one step
2. Move two steps

We recursively compute the minimum total cost for both possibilities and take the smaller result.

For example, from stair i:

minimum cost from i =
cost[i] + min(
    minimum cost from i + 1,
    minimum cost from i + 2
)

Since the same subproblems are recalculated many times, the recursion tree grows exponentially. A stair near the beginning repeatedly recomputes results for the same later stairs.

Although this approach produces the correct answer, it becomes inefficient as the input grows.

Optimal Dynamic Programming Approach

The key observation is that the minimum cost to reach stair i depends only on the minimum costs of the previous two stairs.

If we define:

dp[i] = minimum cost to reach stair i

then:

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

This works because the only ways to reach stair i are:

• From stair i - 1
• From stair i - 2

Instead of recomputing subproblems repeatedly, we compute each state once and store it.

An even better optimization is possible because we only ever need the previous two values. We can replace the entire DP array with two variables, reducing space complexity to constant space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all possible paths
Optimal	O(n)	O(1)	Dynamic programming with rolling variables

Algorithm Walkthrough

1. Handle the first two stairs as base cases.

The minimum cost to reach stair 0 is simply cost[0], because stepping on it requires paying that amount.

Similarly, the minimum cost to reach stair 1 is cost[1]. 2. Create two variables to store the previous DP states.

We use:

• first for the minimum cost to reach stair i - 2
• second for the minimum cost to reach stair i - 1

This avoids allocating an entire DP array. 3. Iterate through the staircase starting from index 2.

For every stair i, calculate:

current = cost[i] + min(first, second)

This represents the cheapest way to arrive at stair i. 4. Shift the rolling variables forward.

After computing current:

• first becomes second
• second becomes current

This prepares the variables for the next iteration. 5. Return the minimum of the final two states.

The top is located beyond the final stair, so we can reach it from either:

• The last stair
• The second-to-last stair

Therefore, the answer is:

min(first, second)

Why it works

The algorithm works because every stair can only be reached from one of the previous two stairs. By storing the minimum cost to reach each stair, we ensure that every future computation builds upon already optimal solutions.

This creates an invariant throughout the iteration:

• first always stores the minimum cost to reach stair i - 2
• second always stores the minimum cost to reach stair i - 1

Using these optimal subproblem solutions guarantees that the computed result is globally optimal.

Python Solution

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        first = cost[0]
        second = cost[1]

        for i in range(2, len(cost)):
            current = cost[i] + min(first, second)
            first = second
            second = current

        return min(first, second)

The implementation begins by initializing the costs for the first two stairs. These act as the base states of the dynamic programming transition.

The loop starts at index 2 because the first two states are already known. For each stair, we compute the minimum total cost required to reach that stair.

The expression:

cost[i] + min(first, second)

represents the current stair's cost plus the cheaper of the two possible previous paths.

After computing the current state, the rolling variables are updated so they continue representing the previous two DP states.

Finally, we return the smaller value between the last two reachable stairs because the top can be reached from either one.

Go Solution

func minCostClimbingStairs(cost []int) int {
    first := cost[0]
    second := cost[1]

    for i := 2; i < len(cost); i++ {
        current := cost[i]

        if first < second {
            current += first
        } else {
            current += second
        }

        first = second
        second = current
    }

    if first < second {
        return first
    }

    return second
}

The Go implementation follows the same dynamic programming logic as the Python version.

Go does not provide a built-in min function for integers in older standard library versions, so the implementation uses explicit comparisons with if statements.

Slices in Go already carry their length information, so iterating through the staircase is straightforward using len(cost).

Integer overflow is not a concern because the maximum possible total cost is well within Go's integer range:

1000 stairs × maximum cost 999 = 999000

Worked Examples

Example 1

cost = [10, 15, 20]

Initial state:

Variable	Value
first	10
second	15

Loop execution:

i	cost[i]	min(first, second)	current	Updated first	Updated second
2	20	10	30	15	30

Final result:

min(15, 30) = 15

Answer:

15

Example 2

cost = [1,100,1,1,1,100,1,1,100,1]

Initial state:

Variable	Value
first	1
second	100

Loop execution:

i	cost[i]	min(first, second)	current	Updated first	Updated second
2	1	1	2	100	2
3	1	2	3	2	3
4	1	2	3	3	3
5	100	3	103	3	103
6	1	3	4	103	4
7	1	4	5	4	5
8	100	4	104	5	104
9	1	5	6	104	6

Final result:

min(104, 6) = 6

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each stair is processed exactly once
Space	O(1)	Only a few variables are stored

The algorithm performs a single pass through the input array. Every iteration performs only constant-time operations, so the total running time grows linearly with the number of stairs.

The space usage remains constant because we store only three variables regardless of input size. No auxiliary arrays or recursive call stacks are required.

Test Cases

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        first = cost[0]
        second = cost[1]

        for i in range(2, len(cost)):
            current = cost[i] + min(first, second)
            first = second
            second = current

        return min(first, second)

solution = Solution()

assert solution.minCostClimbingStairs([10, 15, 20]) == 15
# Basic example with simple optimal choice

assert solution.minCostClimbingStairs(
    [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
) == 6
# Example with many skips of expensive stairs

assert solution.minCostClimbingStairs([0, 0]) == 0
# Minimum input size with zero costs

assert solution.minCostClimbingStairs([5, 10]) == 5
# Minimum input size where starting at index 0 is cheaper

assert solution.minCostClimbingStairs([10, 5]) == 5
# Minimum input size where starting at index 1 is cheaper

assert solution.minCostClimbingStairs([1, 2, 3, 4]) == 4
# Increasing costs

assert solution.minCostClimbingStairs([4, 3, 2, 1]) == 4
# Decreasing costs

assert solution.minCostClimbingStairs([1, 1, 1, 1]) == 2
# Uniform costs

assert solution.minCostClimbingStairs([0, 1, 0, 1]) == 0
# Optimal path skips all paid stairs possible

assert solution.minCostClimbingStairs([999] * 1000) == 499500
# Large input stress test

Test	Why
[10, 15, 20]	Verifies basic example behavior
[1,100,1,1,1,100,1,1,100,1]	Tests repeated optimal skipping
[0,0]	Validates smallest valid input with free stairs
[5,10]	Ensures correct handling of two-element arrays
[10,5]	Ensures alternative starting position is considered
[1,2,3,4]	Tests increasing cost pattern
[4,3,2,1]	Tests decreasing cost pattern
[1,1,1,1]	Tests uniform costs
[0,1,0,1]	Verifies zero-cost skipping behavior
[999] * 1000	Stress test for maximum input size

Edge Cases

One important edge case is the smallest valid input size, where the array contains only two stairs. Since we may start from either stair, the answer is simply the smaller of the two costs. Some incorrect implementations accidentally assume at least three elements exist and attempt invalid indexing. Our implementation handles this naturally because the loop never executes when the array length is two.

Another important edge case involves zero-cost stairs. For example:

[0, 1, 0, 1]

The optimal solution skips every expensive stair possible and pays nothing overall. Greedy implementations that always move one step at a time may fail here. The dynamic programming solution correctly explores both one-step and two-step transitions.

A third important edge case occurs when expensive stairs should be skipped strategically. Consider:

[1, 100, 1, 100, 1]

The optimal path repeatedly jumps over expensive stairs. A naive greedy strategy that chooses the locally cheapest next move can make incorrect decisions because a slightly more expensive immediate choice may lead to a much cheaper total path later. Dynamic programming avoids this issue by computing globally optimal subproblem solutions.

A final edge case is the maximum input size. With 1000 stairs, recursive brute force becomes impractical because of exponential growth in recursive calls. The iterative DP solution processes each stair once, ensuring excellent performance even at the constraint limit.