LeetCode 746: Min Cost Climbing Stairs

Problem Restatement

We are given an array cost.

cost[i] is the price of stepping on stair i.

After paying the cost for a stair, we may climb either:

1 step
2 steps

We can start from stair 0 or stair 1.

We need to return the minimum cost needed to reach the top of the floor.

The top is one position after the last stair.

Input and Output

Example function shape:

def minCostClimbingStairs(cost: list[int]) -> int:
    ...

Examples

Example 1

cost = [10, 15, 20]

Start at stair 1.

Pay:

15

Then climb two steps to the top.

The answer is:

15

Example 2

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

One optimal path pays these stairs:

0, 2, 4, 6, 7, 9

Total cost:

1 + 1 + 1 + 1 + 1 + 1 = 6

The answer is:

6

First Thought: Try Every Path

From each stair, we can move either one step or two steps.

This creates many possible paths.

A recursive brute force solution would try both choices from every position.

That repeats the same subproblems many times.

For example, the minimum cost from stair 5 may be computed from different earlier paths.

We need dynamic programming.

Key Insight

To reach stair i, the previous stair must be either:

i - 1

or:

i - 2

So the minimum cost to reach stair i depends only on the two previous states.

Let:

dp[i]

mean the minimum cost needed to reach position i.

Position i may be a real stair, or the top.

The top is:

len(cost)

To reach i, we either come from i - 1 and pay cost[i - 1], or come from i - 2 and pay cost[i - 2].

So:

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

The start is free from stair 0 or stair 1, so:

dp[0] = 0
dp[1] = 0

Algorithm

1. Let n = len(cost).
2. Create dp with size n + 1.
3. Set dp[0] = 0 and dp[1] = 0.
4. For every position i from 2 to n:
   • compute the cheaper way to reach i.
5. Return dp[n].

Correctness

dp[i] stores the minimum cost to reach position i.

For the base cases, dp[0] = 0 and dp[1] = 0 are correct because the problem allows us to start from stair 0 or stair 1 without paying before standing there.

For any position i >= 2, the last move into i must come from either i - 1 or i - 2, because each move climbs one or two steps. If we come from i - 1, we must pay cost[i - 1]. If we come from i - 2, we must pay cost[i - 2].

The recurrence takes the minimum of these two valid possibilities, so it gives the minimum cost to reach i.

Since the DP computes positions from smaller to larger, both previous states are already correct when computing dp[i].

Therefore dp[n] is the minimum cost to reach the top.

Complexity

Let n = len(cost).

Implementation

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            dp[i] = min(
                dp[i - 1] + cost[i - 1],
                dp[i - 2] + cost[i - 2],
            )

        return dp[n]

Code Explanation

We create one DP state for every stair position plus the top:

dp = [0] * (n + 1)

The top is index n.

The loop starts at 2 because 0 and 1 are free starting positions:

for i in range(2, n + 1):

For each position, we choose the cheaper previous step:

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

Finally, return the cost to reach the top:

return dp[n]

Space-Optimized Implementation

Only the previous two DP values are needed.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        prev2 = 0
        prev1 = 0

        for i in range(2, len(cost) + 1):
            current = min(
                prev1 + cost[i - 1],
                prev2 + cost[i - 2],
            )

            prev2 = prev1
            prev1 = current

        return prev1

This version uses constant extra space.

Testing

def run_tests():
    s = Solution()

    assert s.minCostClimbingStairs([10, 15, 20]) == 15
    assert s.minCostClimbingStairs(
        [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    ) == 6

    assert s.minCostClimbingStairs([0, 0]) == 0
    assert s.minCostClimbingStairs([1, 2]) == 1
    assert s.minCostClimbingStairs([5, 10, 5]) == 10
    assert s.minCostClimbingStairs([10, 1, 10, 1, 10]) == 2

    print("all tests passed")

run_tests()