Robot on the Staircase

A delivery robot climbs a staircase of n steps. In one move it can climb 1, 2 or 3 steps. In how many different ways can it reach exactly step n? (Order of moves matters.)

Examples

Example 1

Input:  n = 1
Output: 1

A staircase of one step can only be climbed by a single 1-step move; the 2- and 3-step moves would overshoot. So there is exactly 1 way.

Example 2

Input:  n = 3
Output: 4

Constraints

n is the number of steps, 0 or more. The answer grows very fast, so it is returned as a long.

Two ways count as different when the order of the moves differs: 1 + 2 and 2 + 1 are two ways. There is exactly one way to be at step 0 — do nothing.

How to solve it

Hint

“Number of ways to reach step n” where the last move was 1, 2 or 3 steps → ways(n) = ways(n−1) + ways(n−2) + ways(n−3).

Approach: 1-D DP · counting ways

State: i = steps still to climb (or current step).
Choices: take 1, 2 or 3 steps.
Base: 0 steps left → 1 way; negative → 0 ways.

Complexity: Plain: O(3ⁿ) · Memo: O(n) time, O(n) space.

The reference solutions in all four languages are in the Solutions tab of the workspace below.