3
n
Each stair has a cost; you can jump 1 or 2 steps. Find the cheapest path to exit the staircase. A textbook one-dimensional DP problem — the recurrence is dp[i] = cost[i] + min(dp[i-1], dp[i-2]), and the answer collapses to just two rolling variables.
Given an integer array cost where cost[i] is the fee to step off stair i, return the minimum total cost to reach the floor beyond the top of the staircase. You may start at index 0 or 1, and from any stair you can climb 1 or 2 steps.
Concrete example. cost = [10, 15, 20]. Three stairs. If you start at index 1 (cost 15) and jump 2, you exit paying only 15. Alternatively start at 0 (cost 10) then take stair 2 (cost 20) — total 30. The answer is 15.
n), not the last stair itself. So the answer is min(dp[n-1], dp[n-2]), not dp[n-1]. Many off-by-one mistakes come from forgetting you can also jump the last two steps in one go.i is cost[i] + min(cheapest to reach i-1, cheapest to reach i-2). Once you know the two previous costs, you can compute the current one in O(1). This is the entire algorithm — a recurrence you evaluate left-to-right in a single pass.dp[0] = cost[0] and dp[1] = cost[1] — stepping off the first two stairs has no predecessor dependency.i = 2 … n-1, compute dp[i] = cost[i] + min(dp[i-2], dp[i-1]). Each cell needs only the previous two.prev2 and prev1. After each step, shift: prev2 = prev1, prev1 = cur.min(prev2, prev1) — you could exit from either of the last two stairs.dp[i] depends only on dp[i-1] and dp[i-2]: Fibonacci, Climbing Stairs (LC 70), House Robber (LC 198), Decode Ways (LC 91). Once you spot that shape, drop the array and go O(1) space immediately.The full dp[] array is O(n) space and perfectly fine in an interview. The rolling-variable form reduces to O(1) space with zero change to the logic — just rename dp[i-2] → prev2 and dp[i-1] → prev1. Prefer the array form first for clarity, then optimise when asked.
n = 3. Seed the two base cases: prev2 = cost[0] = 10 (dp[0]) and prev1 = cost[1] = 15 (dp[1]). You may start at index 0 or index 1.1▶function minCostClimbingStairs(cost: number[]): number {2▶ const n = cost.length;3 // dp[i] = minimum cost to step off stair i4▶ let prev2 = cost[0]; // dp[i-2]5▶ let prev1 = cost[1]; // dp[i-1]67 for (let i = 2; i < n; i++) {8 const cur = cost[i] + Math.min(prev2, prev1);9 prev2 = prev1;10 prev1 = cur;11 }1213 // Can reach the top from the last or second-to-last stair14 return Math.min(prev2, prev1);15}
function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
// dp[i] = minimum cost to step off stair i
let prev2 = cost[0]; // dp[i-2]
let prev1 = cost[1]; // dp[i-1]
for (let i = 2; i < n; i++) {
const cur = cost[i] + Math.min(prev2, prev1);
prev2 = prev1;
prev1 = cur;
}
// Can reach the top from the last or second-to-last stair
return Math.min(prev2, prev1);
}cost[0] and cost[1]. These become the initial prev2 and prev1.cur = cost[i] + min(prev2, prev1) is the cheapest way to step off stair i. Then we slide the window: prev2 = prev1, prev1 = cur. The array never needs to exist in memory.prev2 holds dp[n-2] and prev1 holds dp[n-1]. Because you can jump 1 or 2 steps off the last stair, the answer is min(prev2, prev1).cost. O(1) space — two scalar variables replace the full DP table.k (a monotonic deque gives O(n) total).dp[] explicitly, then backtrack: at each stair check which predecessor gave the minimum, and walk from n-1 (or n-2) back to the chosen start.function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
// dp[i] = minimum cost to step off stair i
let prev2 = cost[0]; // dp[i-2]
let prev1 = cost[1]; // dp[i-1]
for (let i = 2; i < n; i++) {
const cur = cost[i] + Math.min(prev2, prev1);
prev2 = prev1;
prev1 = cur;
}
// Can reach the top from the last or second-to-last stair
return Math.min(prev2, prev1);
}cost. O(1) space — two scalar variables replace the full DP table.From the top, ask the cost to reach each stair recursively: it's that stair's cost plus the cheaper of arriving from one or two stairs below — the recurrence stated directly, with no memo table.
function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
// minToReach(i) = minimum cost to be standing on stair i.
const minToReach = (i: number): number => {
if (i < 0) return 0; // before the staircase: free
if (i === 0 || i === 1) return cost[i]; // can start here directly
return cost[i] + Math.min(minToReach(i - 1), minToReach(i - 2));
};
// The top is one past the last stair; reach it from n-1 or n-2.
return Math.min(minToReach(n - 1), minToReach(n - 2));
}O(2ⁿ) nodes and recomputes the same stairs endlessly. Memoizing on i (or rolling two variables bottom-up) collapses it to O(n).| "minimum cost" + 1-or-2 step jumps | 1-D DP: dp[i] = cost[i] + min(prev, prev2) |
| dp[i] depends only on dp[i-1] and dp[i-2] | two rolling variables → O(1) space |
| "you can start at index 0 or 1" | answer = min(dp[n-2], dp[n-1]) |
| staircase, frog jump, house robber shape | Fibonacci-family DP pattern |
function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
let prev2 = cost[0];
let prev1 = cost[1];
for (let i = 2; i < n; i++) {
const cur = cost[i] + Math.min(prev2, prev1);
prev2 = prev1;
prev1 = cur;
}
return Math.min(prev2, prev1);
}dp[i] = cost[i] + min(dp[i-1], dp[i-2])— pay the stair's cost plus the cheapest arrival.cost = [10, 15, 20], what is the minimum cost to reach the top?i, what values do prev2 and prev1 hold?