Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
Count ordered sequences of moves of length 1, 2, or 3 that advance exactly n positions. For n = 3, the sequences are [1, 1, 1], [1, 2], [2, 1], and [3], giving four. Zero has one sequence, the empty sequence. A negative target has no valid sequence and returns zero.
Group sequences by their final move
A sequence ending at position n must end with a move of 1, 2, or 3. Removing that final move leaves a sequence ending at n - 1, n - 2, or n - 3 respectively. Conversely, appending the corresponding final move to any sequence for one of those positions creates a valid sequence for n.
The three groups are disjoint because their final moves differ. Add their counts to obtain ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3). This counts order: [1, 2] and [2, 1] belong to different final-move groups. Counting unordered combinations would require a different state and iteration rule.
Initialize the empty sequence correctly
Set the count for position zero to one. Without that seed, the recurrence would multiply an all-zero history into all-zero answers. Positions below zero contribute zero because a positive-length move cannot arrive there from the start. The first positive counts are one for n = 1, two for n = 2, and four for n = 3.
The chosen implementation keeps only three rolling values instead of a full table. At each iteration, their sum becomes the next count. Shift the older values backward and store the new sum as the most recent value. After n iterations, the most recent value represents exactly position n.
Trace enough steps to check the shift
Start with history for positions -2, -1, and 0 equal to 0, 0, and 1. The next sum is 1, leaving history 0, 1, 1. The next sum is 2, leaving 1, 1, 2. The next sum is 4, leaving 1, 2, 4. Position four then has 1 + 2 + 4 = 7 sequences.
Compute the sum before overwriting any history value. Updating the most recent count too early can make later assignments reuse the new count twice. A trace that names the represented positions exposes that error more clearly than a trace of unnamed variables alone.
Explain the improvement over recursion
A direct recursive function follows the recurrence literally and repeatedly recomputes the same positions. Memoization reduces that repetition to one computation per position. Bottom-up iteration also computes each position once and removes recursive frames. Since only the previous three counts are needed, rolling state reduces auxiliary storage further.
The selected version takes O(n) additions and O(1) stored counts under bounded-integer arithmetic. Counts grow quickly. Once they exceed a language's integer range, overflow can corrupt the answer or trap. Arbitrary-precision integers avoid that fixed bound but make arithmetic cost and numeric storage grow with the answer's digit length.
Test ordering and boundary values
Test negative targets, zero, one, two, three, and four. Values 0 and 3 reject common incorrect base cases. Compare short targets with an independent recursive enumeration that records every complete move sequence and counts it. Keep that oracle's inputs small because it intentionally generates exponentially many paths.
A follow-up can permit an arbitrary set of positive move lengths. The recurrence sums counts from each allowed predecessor position, with time proportional to n times the number of allowed moves. Zero or negative move lengths need separate restrictions because they can create cycles or infinitely many sequences. If the task instead asks for a shortest sequence, replace the counting objective with a minimum-distance recurrence.
Continue with the implementation
Read the JavaScript walkthrough for the current code and links to the other programming languages. Use the original lesson for practice.