Min Cost Climbing Stairs

Problem

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: 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
Explanation: 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 1: Dynamic Programming (Bottom-Up)

The key insight is that the minimum cost to reach step i is the cost at step i plus the minimum of the costs to reach the previous two steps.

Implementation

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)

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

        return min(cost[-1], cost[-2])

Approach 2: DP with Separate Array (Non-Destructive)

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

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

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

        return min(dp[-1], dp[-2])

Approach 3: Space-Optimized DP

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev2 = cost[0]
        prev1 = cost[1]

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

        return min(prev1, prev2)

Complexity Analysis

Time Complexity: O(n), where n is the length of cost array.
Space Complexity: O(1) for space-optimized version, O(n) for versions with dp array.

Key Insights

Optimal Substructure: The minimum cost to reach step i depends on the minimum costs to reach steps i-1 and i-2.
Top is Beyond Array: The “top” is one step beyond the last index, so we can reach it from either of the last two steps.
Starting Options: We can start from index 0 or 1, which is why both are initialized with their respective costs.
In-Place Modification: We can modify the input array to save space, computing cumulative minimum costs.
Final Answer: Return the minimum of the last two values, as we can reach the top from either position.