Climbing Stairs

Learning goal: Translate the staircase story into a counting problem over smaller destinations.

Core idea A valid route to step n must finish with either a one-step move from n - 1 or a two-step move from n - 2. These two groups are disjoint because their final moves differ, so we can add their counts. The important question is not which route we personally choose, but how many routes reach each earlier step.

Model the answer

Let f(k) be the number of distinct move sequences that reach step k. The target is f(n), not the length of one particular route.

Micro-example For n = 4, routes ending in one step contribute f(3), while routes ending in two steps contribute f(2). Therefore f(4) = f(3) + f(2) = 3 + 2 = 5.

Pitfalls

• Do not count only the number of ways to choose step sizes; order matters.
• A route such as 1+2 differs from 2+1.
• Define the base cases before applying the recurrence.

Recap

• Count routes to each step with f(k).
• Every route to k comes from exactly one of k - 1 or k - 2.
• The final answer is f(n).

Learning goal: Derive the recurrence that makes the dynamic program correct.

Core idea Partition all routes to step k by their final move. If the last move is size one, the earlier portion is any route to k - 1. If the last move is size two, the earlier portion is any route to k - 2. Since every route has exactly one final move, these cases cover every route once.

Recurrence

Micro-example f(2) = f(1) + f(0) = 1 + 1 = 2, representing 11 and 2. Then f(3) = f(2) + f(1) = 2 + 1 = 3.

Pitfalls

• Using f(0) = 0 breaks the count for a final two-step move.
• Adding f(k - 1) and f(k - 2) is valid only because the final move partitions the routes.
• Keep the indexing convention consistent with the base cases.

Recap

• The recurrence is Fibonacci-shaped.
• Base values are f(0) = 1 and f(1) = 1.
• Each state depends only on the previous two states.

Learning goal: Implement the recurrence with O(1) extra space.

Core idea A full DP array would store every value from f(0) through f(n), but the next value needs only the previous two. Maintain two rolling variables: prev2 = f(k - 2) and prev1 = f(k - 1). After computing next, shift the pair forward.

Algorithm plan

• Initialize prev2 = 1 and prev1 = 1.
• Repeat for destinations 2 through n.
• Compute next = prev1 + prev2.
• Shift: set prev2 = prev1, then prev1 = next.
• Return prev1.

def climb_stairs(n):
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Micro-example For n = 5, the values progress as 1, 1, 2, 3, 5, 8. At the end, prev1 stores f(5).

Pitfalls

• Run the loop through n, including the destination step.
• Update both rolling values together so the old prev1 is not lost.
• Handle n = 1 with the initial values and zero loop iterations.

Recap

• Bottom-up order ensures both dependencies are ready.
• Two variables replace the full DP array.
• Time is O(n) and extra space is O(1).

Learning goal: Trace every rolling update until the answer for n = 5 is produced.

Core idea We begin with the two base values and compute one destination at a time. At each iteration, the pair represents adjacent DP states; after the shift, it represents the next adjacent pair. This preserves exactly the information needed by the recurrence while discarding older values.

State meaning

Micro-example For n = 5: f(2) = 2, f(3) = 3, f(4) = 5, and f(5) = 8. The final rolling pair is prev2 = 5, prev1 = 8.

Pitfalls

• At f(3), use the updated pair (f(1), f(2)), not the original bases.
• The answer for n = 5 is 8, not the previous value 5.
• The sequence starts with two ones under this boundary convention.

Recap

• Each update adds the two current values.
• Shifting maintains the DP invariant.
• The walkthrough ends with f(5) = 8.

Learning goal: Recognize why the efficient recurrence is preferable to naive recursion.

Core idea A direct recursive definition branches into calls for n - 1 and n - 2. Those branches repeatedly ask for the same smaller values, so the call tree grows exponentially. Dynamic programming avoids this duplication by computing each state once and reusing it.

Compare the approaches

Micro-example A recursive call for f(5) asks for f(4) and f(3). The f(4) branch asks for f(3) again, duplicating work immediately.

Pitfalls

• Do not use plain recursion unless memoization is added.
• Do not confuse O(1) auxiliary space with the input value n.
• Test n = 1 so the loop boundary does not create an invalid state.

Recap

• Memoization or bottom-up DP removes repeated work.
• Rolling variables preserve linear time with constant extra space.
• Small inputs still deserve explicit boundary-case checks.

Learning goal: Justify the final complexity and summarize the reusable DP pattern.

Core idea The loop performs one constant-time addition for each destination from 2 through n. The algorithm stores only two integer values, regardless of how large n is within the constraint range. Thus it is both time-efficient and memory-efficient.

Why the bounds hold

• There are n - 1 loop iterations, each taking O(1) time.
• The initialization, addition, shifting, and return are all constant-time operations.
• Only prev2, prev1, and a temporary sum are stored.

Micro-example For n = 5, the algorithm performs four recurrence updates and returns 8. Increasing n adds one constant-time update per step, not a new branch of recursive work.

Pitfalls

• Report auxiliary space as O(1), not O(n), because no array is retained.
• The output grows with n, but that does not change the number of stored variables in this problem.
• Keep the recurrence and base-case convention aligned in both explanation and code.

Recap

• Recurrence: f(n) = f(n - 1) + f(n - 2).
• Bottom-up rolling DP: O(n) time and O(1) extra space.
• Avoid plain recursion without memoization because it is exponential.