Here is solutions for Min Cost Climbing Stairs.

1. Understand the problem

• You are given an array cost, where:

  • cost[i] = cost of stepping on the i-th stair.

  • You can start from step 0 or step 1.

  • From any step i, you can move to:

    • i + 1 (1 step)

    • i + 2 (2 steps)

  • You must reach just beyond the last index (the “top”).

  • You only pay the cost of the step you land on, not the top.

• 👉 Goal: Return the minimum total cost to reach the top.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Minimum input size?

• 2 ≤ len(cost) ≤ 1000

1. Can costs be zero?

• Yes, 0 ≤ cost[i] ≤ 999

1. Do we pay cost at the top?

• ❌ No, only when stepping on indices 0 … n-1.

1. Can we start before index 0?

• ✅ Yes, we conceptually start at step 0 or 1 for free.

1. Are negative costs allowed?

• ❌ No, all costs are non-negative.

3. Explore examples.

1. Example 1

cost = [10, 15, 20]

Possible:

- Start at 0 → pay 10 → jump to top → total = 10

- Start at 1 → pay 15 → jump to top → total = 15

✅ Answer = 10

1. Example 2

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

Optimal path:

1 → 1 → 1 → 1 → 1 → 1 = 6

✅ Answer = 6

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. 🧠 Solution 1 — Naive Recursion (Brute Force) - Time O(2^N), Space O(N)

• Idea:

  At each index, try both:

  • 1 step forward

  • 2 steps forward

  • Return minimum.

• State: dfs(i) = min cost from step i to top.

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

• Time: O(2^n) ❌ TLE

• Space: O(n) recursion stack, but Time O(2^N) is number of choices at the time.

4.2.🧠 Solution 2 — DP with Array (Top-Down or Bottom-Up) - Time O(N), Space O(N)

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

• Time: O(N).

• Space: O(N).

4.3. Solution 3 — Space Optimized DP (Best) - Time O(N), Space O(1)

cur = min(prev1 + cost[i-1],
          prev2 + cost[i-2])

• Time: O(N).

• Space: O(1).

5. Implement solutions.

5.1. Recursion - Time O(2^N), Space O(N)

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

        def dfs(i):
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))

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

• Time: O(2^N).

• Space: O(N).

5.2. Dynamic Programming (Top-Down) - Time O(N), Space O(N)

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

        def dfs(i):
            if i >= len(cost):
                return 0
            if memo[i] != -1:
                return memo[i]
            memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
            return memo[i]

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

• Time: O(N).

• Space: O(N).

5.3. Dynamic Programming (Bottom-Up) - Time O(N), Space O(N)

• Idea: Build from 0-index

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]

• Time: O(N).

• Space: O(N).

5.4. Dynamic Programming (Space Optimized) - Time O(N), Space O(1)

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

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

        return prev1

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])

        return min(cost[0], cost[1])

• Time: O(N)

• Space: O(1)

6. Notes for DP

• Idea

  • If dp[i] depends on smaller indices → go LEFT → RIGHT
  • If dp[i] depends on larger indices → go RIGHT → LEFT

• Forward DP: “I am building the answer step by step from the start.”

dp[i] = min cost to reach i
dp[i] depends on dp[i-1], dp[i-2]

• Backward DP: “If I start here, what is the best result to the end?”

dp[i] = min cost to reach top from i
dp[i] = cost[i] + min(dp[i+1], dp[i+2])

=> Both are valid — just different state definitions.

• 2D Grid/Interval DP: depend in multiple-axises

7. Dry run examples

✅ Dry Run 1 cost = [10, 15, 20]

n = 3

prev2 = 0 # dp[0]
prev1 = 0 # dp[1]

i = 2

cur = min(prev1 + cost[1], prev2 + cost[0])
= min(0 + 15, 0 + 10)
= 10

i = 3 prev2 = 0 prev1 = 10

cur = min(prev1 + cost[2], prev2 + cost[1])
= min(10 + 20, 0 + 15)
= 15

prev2 = 10 prev1 = 15

✅ Answer = 15

Optimal path:

Start at step 1 → pay 15 → top