Min Cost Climbing Stairs - Video Solutions

Problem Overview: You are given an array cost where cost[i] represents the cost of stepping on the i-th stair. You can climb either one or two steps at a time, and you may start from step 0 or step 1. The goal is to reach the top of the staircase (one step beyond the last index) with the minimum total cost.

Approach 1: Dynamic Programming with Table (O(n) time, O(n) space)

This approach models the problem using dynamic programming. Define dp[i] as the minimum cost required to reach step i. Since you can arrive at step i from either i-1 or i-2, the recurrence becomes dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Start with dp[0] = 0 and dp[1] = 0 because you can begin from either step without paying a cost. Iterate through the array, computing the optimal cost for each position until you reach the top. This approach clearly shows the subproblem structure and is easy to reason about during interviews. Time complexity is O(n) because each step is processed once, and space complexity is O(n) for the DP table.

Approach 2: Optimized Dynamic Programming with Constant Space (O(n) time, O(1) space)

The transition only depends on the previous two states, so storing the entire DP table is unnecessary. Track just two variables representing the minimum cost to reach the previous two steps. For each new step, compute the current minimum using the same recurrence: current = min(prev1 + cost[i-1], prev2 + cost[i-2]). Then shift the variables forward for the next iteration. This reduces memory usage while preserving the same logic as the table-based solution. The algorithm still iterates once through the input array, giving O(n) time complexity and O(1) extra space.

The key insight is recognizing overlapping subproblems. The minimum cost to reach a step depends only on the two steps before it, which makes the problem a classic dynamic programming pattern similar to Fibonacci-style state transitions.

Recommended for interviews: Start by explaining the DP state definition and recurrence using the table approach. It demonstrates that you understand how to break the problem into subproblems. Then optimize the solution by keeping only the last two states to achieve constant space. Interviewers typically expect the O(n) time and O(1) space dynamic programming solution.