Baseline Dynamic Programming · 1D DP O(n) · O(1)
A warehouse robot services a loading dock with n steps. Its wheel base lets it advance exactly one or two steps per move, and its route planner logs every distinct sequence of moves that reaches the top. The fleet manager wants to know how many different climb patterns exist for a dock of any height, so crews can budget inspection time per route variant.
Input: A single integer n, the number of steps in the staircase.
Output: Return the number of distinct move sequences that reach step n.
1 <= n <= 45Input: {"n":2}
Output: 2
1+1 or a single 2-step leap.
Input: {"n":3}
Output: 3
1+1+1, 1+2, and 2+1 — the count is f(2) + f(1) = 2 + 1.