Climbing Stairs

A staircase has n steps. From the ground you may move +1 or +2 steps at each move. Count how many distinct sequences of moves end exactly on step n.

Let dp(n) = number of ways to reach step n (with dp(0) = 1 meaning one way to be at the start before the first move).

For n ≥ 1, your last move is either from step n − 1 (a 1-step) or from n − 2 (a 2-step), and those cases are disjoint:

Explanation: Every path to step n must arrive from n−1 or n−2 exactly once; summing those two counts counts every path once.

Keep memo[0…n] with a sentinel (e.g. −1) for “unknown.” When dp(n) is needed, return memo[n] if it is already set; otherwise compute dp(n) using the recurrence on smaller indices, assign memo[n], then return.

Only n + 1 states exist, so the work is O(n).

With dp(0) = 1 (one empty path at the ground):

For n ≥ 3, only the recurrence applies. Alternatively, you can define dp(1) = 1, dp(2) = 2 directly and use the recurrence for n ≥ 3 — match your indexing to your implementation.

Top-down with memo:

Time: O(n). Space: O(n) for memo and recursion depth.