#746

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Min Cost Climbing Stairs

Compute the minimum cost to reach the top of a staircase using dynamic programming and step-by-step state transitions efficiently.

array dynamic programming

Problem Statement

You are given an integer array 'cost' where cost[i] represents the cost of stepping on the i-th stair. You may move up one or two steps after paying the cost of the current stair. The goal is to reach the top of the staircase while minimizing total expenditure, following clear state transitions for each step.

You can choose to start at either step index 0 or step index 1. Return the minimum total cost required to reach just beyond the last step, leveraging dynamic programming to track the optimal path for each state.

Examples

Example 1

Input: cost = [10,15,20]

Output: 15

You will start at index 1.

Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

You will start at index 0.

Pay 1 and climb two steps to reach index 2.
Pay 1 and climb two steps to reach index 4.
Pay 1 and climb two steps to reach index 6.
Pay 1 and climb one step to reach index 7.
Pay 1 and climb two steps to reach index 9.
Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints

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

Solution Approach

Dynamic Programming with Bottom-Up Array

Create an array dp where dp[i] represents the minimum cost to reach the i-th step. Initialize dp[0] = cost[0] and dp[1] = cost[1]. Then, for each step i from 2 to n-1, set dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The minimum cost to reach the top is min(dp[n-1], dp[n-2]).

Space Optimization

Since each dp[i] only depends on dp[i-1] and dp[i-2], maintain two variables instead of the full array to track these values. Iteratively update them while computing the minimum cost to reach each step, achieving O(1) space while keeping O(n) time complexity.

Iterative State Transition Verification

Walk through the cost array manually for small examples to validate the DP transitions. Ensure each step considers both one-step and two-step moves, confirming that the cumulative minimum cost matches expected outputs, which helps catch off-by-one or index selection errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because we iterate through each step once, and space complexity can be O(n) with the full DP array or optimized to O(1) by storing only the last two states. This trade-off is specific to state transition dynamic programming patterns where only previous states affect the current computation.

What Interviewers Usually Probe

Asks how you handle both starting indices 0 and 1 to ensure minimal cost.
Questions about optimizing space while preserving correct state transitions.
Wants explanation of why dp[i] = cost[i] + min(dp[i-1], dp[i-2]) captures all possible paths efficiently.

Common Pitfalls or Variants

Common pitfalls

Confusing array indices and overstepping boundaries when computing dp[i].
Failing to account for starting from index 1, which may yield a lower total cost.
Attempting to reconstruct the path instead of just computing minimum cost, which can overcomplicate the solution.

Follow-up variants

Climbing stairs with variable maximum step size per stair.
Min cost climbing stairs with constraints on consecutive step selections.
Counting the number of distinct minimum-cost paths to reach the top.

FAQ

What is the main pattern used in Min Cost Climbing Stairs?

The problem follows a state transition dynamic programming pattern where each step's cost depends on the previous two steps.

Can I start from index 1 instead of index 0?

Yes, starting from index 1 may result in a lower total cost, and the solution must consider both starting points.

What is the time and space complexity of this solution?

Time complexity is O(n). Space can be O(n) with a full DP array or O(1) with space optimization using two variables.

How do I handle small cost arrays efficiently?

Iteratively compute dp[i] for each step while considering both one-step and two-step moves to ensure minimal cost even for small arrays.

Are there common mistakes when implementing this DP?

Yes, common errors include miscalculating indices, ignoring the starting step choices, and unnecessarily tracking the path instead of cost only.

terminal

Solution

Solution 1: Memoization Search

We design a function $\textit{dfs}(i)$, which represents the minimum cost required to climb the stairs starting from the $i$-th step. Therefore, the answer is $\min(\textit{dfs}(0), \textit{dfs}(1))$.

1

2

3

4

5

6

7

8

9

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))

        return min(dfs(0), dfs(1))

Solution 2: Dynamic Programming

We define $f[i]$ as the minimum cost needed to reach the $i$-th stair. Initially, $f[0] = f[1] = 0$, and the answer is $f[n]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))

        return min(dfs(0), dfs(1))

Solution 3: Dynamic Programming (Space Optimization)

We notice that the state transition equation for $f[i]$ only depends on $f[i - 1]$ and $f[i - 2]$. Therefore, we can use two variables $f$ and $g$ to alternately record the values of $f[i - 2]$ and $f[i - 1]$, thus optimizing the space complexity to $O(1)$.

1

2

3

4

5

6

7

8

9

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))

        return min(dfs(0), dfs(1))

Continue Practicing

#741 cherry pickup #740 delete and earn #764 largest plus sign