💬 Discord
Sign In
NeetCode #658LC-746Easy1-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#658 · #746 · Min Cost Climbing Stairs(使用最小花费爬楼梯)

📌 Problem Statement & Constraints

You are given an integer array cost where cost[i] is the price of stepping on stair i. Once you pay, you may climb one or two steps. You may start at index 0 or 1, and the top is one step past the last index. Return the minimum cost to reach the top. Constraints: 2 <= cost.length <= 1000, 0 <= cost[i] <= 999.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the minimum cost to stand on stair i.
  2. You arrive at i from i - 1 or i - 2, and you pay cost[i] only when you step on i: dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]).
  3. The top is index n, which has no cost of its own, so the answer is min(dp[n - 1], dp[n - 2]).
  4. Two rolling variables replace the array, giving O(1) space.

💻 Benchmark Python3 Implementation

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        prev2, prev1 = cost[0], cost[1]     # dp[i-2], dp[i-1]
        for i in range(2, len(cost)):
            cur = cost[i] + min(prev2, prev1)
            prev2, prev1 = prev1, cur
        return min(prev2, prev1)            # the top is one past the last index

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the stairs.
💾 Space Complexity
O(1): two rolling values.

⚠️ Interview Pitfalls & Follow-ups

  • Returning dp[n - 1]: the top is index n, reachable from either n - 1 or n - 2, so the answer is their minimum.
  • Adding a cost for the top: the top step is free; only stairs you actually stand on cost money.
  • Initialising both base cases to cost[0]: dp[1] = cost[1] because you are allowed to start directly on stair 1.
  • Building a full DP array: two variables suffice, since each state depends on only two predecessors.