Basic Problemscountinglinear

Climbing Stairs with 3 Moves

You climb a staircase of n steps, and each move goes up 1, 2, or 3 steps. Count the distinct routes to the top. The staircase is the same as the flagship lesson's; only your move set grew.

Do this lesson first: climbing stairs

Example input

n = 7

Expected output

44

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

Ask what the last move could have been, the same question the flagship lesson asks. A move of 1, 2, or 3 steps is now legal, so the last move into stair i came from exactly one of three places: stair i-1, i-2, or i-3. Three buckets, added rather than compared, because there is no choice to optimize, only routes to count.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = dp[1] = 1 and dp[2] = 2 are given directly; a third base case is needed because the recurrence now reaches three cells back, and dp[2] would be wrong if it were derived from a two-term rule instead of stated outright (see the pitfall). Every other cell depends only on smaller indices, so filling left to right still guarantees all three dependencies exist before they are read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

1

2

4

7

13

24

44

climbing-stairs-three-moves.ts

1function climbStairsThreeMoves(n) {
2 const dp = [1, 1, 2];
3 for (let i = 3; i <= n; i++) {
4 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
5 }
6 return dp[n];
7}

Base caseComputedBeing readAnswer

The code, the trap, the variations

climbing-stairs-three-moves.ts

1function climbStairsThreeMoves(n) {
2 const dp = [1, 1, 2];
3 for (let i = 3; i <= n; i++) {
4 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
5 }
6 return dp[n];
7}

Where people go wrong

Treating dp[2] as derivable from dp[1] + dp[0], the way the flagship two-move staircase would. Under three moves dp[2] is still 2 (a single move of 2, or two moves of 1), but the three-term recurrence does not apply until i = 3; stating dp[0], dp[1], and dp[2] outright avoids folding a rule into a cell it was never meant to reach.

Restrict moves back to just 1 or 2 steps.
That is the flagship Climbing Stairs: one fewer bucket, one fewer base case, same left-to-right order.
Allow moves of 1, 2, 3, or 4 steps.
A fourth bucket and a fourth base case join the sum. The state and the order stay untouched; only how many prior cells the last move can have come from grows.

Climbing Stairs Weighted Climbing Stairs