5
n
Each step can be reached from the one or two steps below it, so the number of ways follows the Fibonacci recurrence — and with two rolling variables you solve it in O(n) time and O(1) space.
You can climb either 1 or 2 stairs at a time. Given n stairs, count the distinct ways to reach the top. n = 5: the answer is 8 (the 5th Fibonacci-like number: 1, 1, 2, 3, 5, 8). For n = 3 the three sequences are 1+1+1, 1+2, 2+1 → 3 ways.
i you must have come from step i−1 (one-step jump) or step i−2 (two-step jump). Therefore ways(i) = ways(i−1) + ways(i−2) — the Fibonacci recurrence. The whole problem collapses to a lookup table that fills left-to-right.dp[1] = 1 (one way to reach step 1), dp[2] = 2 (1+1 or 2).dp[i] = dp[i−1] + dp[i−2] for i ≥ 3. Each cell only needs the two before it.prev2, prev1) and discard the rest. Array size drops from O(n) to O(1).dp[n] (or prev1 in the rolling version).dp[1] = 1 and dp[2] = 2, not dp[0] = 0, dp[1] = 1 like standard Fibonacci. Getting these wrong shifts every answer by one. A clean way to avoid the mistake: initialize the rolling variables as prev2 = 1, prev1 = 2 and start the loop at i = 3.The O(n) DP with an explicit array is fine at interview, but the rolling-variable version showcases the insight that only two prior values are needed. There is also a closed-form O(log n) matrix exponentiation approach for very large n, but it is rarely asked.
dp[i] = max(dp[i−1], dp[i−2]+nums[i])), Min Cost Climbing Stairs, and Decode Ways(two conditionals feeding the same rolling frame). Any “two choices at each step, no going back” DP reduces to this shape.dp[0] = 1 (one way to stand at ground) and dp[1] = 1 (one way to reach step 1). Array is dp[0..5].function climbStairs(n: number): number {
if (n <= 2) return n;
let prev2 = 1; // ways to reach step 1
let prev1 = 2; // ways to reach step 2
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}n ≤ 2 the answer is n itself (1 way for n=1, 2 ways for n=2). Returning early keeps the loop simple.prev2 = 1 holds dp[1] and prev1 = 2 holds dp[2]. These are the two prior values the recurrence always needs.curr = prev1 + prev2 is the recurrence. Then shift: prev2 ← prev1 and prev1 ← curr. After the loop, prev1 holds dp[n].prev1 is the answer. If you used an array you would return dp[n]; the rolling variable is exactly that, compressed.prev2 and prev1 are sufficient.dp[i] = dp[i−1] + dp[i−2] + dp[i−3] and keep three rolling variables.cost[i] inside the recurrence.parent[] array tracking which predecessor gave the max count, then backtrack from n to reconstruct one valid path.climbStairs(n) = climbStairs(n−1) + climbStairs(n−2). It's O(2ⁿ) without memoization — the same sub-problems get recomputed on every branch.| "1 or 2 steps at a time" | Fibonacci / rolling-variable DP |
| count distinct paths with two move sizes | dp[i] = dp[i−1] + dp[i−2] |
| "min cost" or "max loot" at each step | same frame, swap + for max/min |
| dp recurrence references only k prior cells | k rolling variables → O(1) space |
if (n <= 2) return n;
let prev2 = 1; // dp[1]
let prev1 = 2; // dp[2]
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;dp[i] = dp[i−1] + dp[i−2] — ways from one step below plus ways from two steps below.climbStairs(5)?prev1 holds:climbStairs(n) without memoization run in O(2ⁿ)?climbStairs(1) should return: