448. The Three-Step Sequence
A sequence starts T(0) = 0, T(1) = 1, T(2) = 1, and every later term is the
sum of the THREE before it. Print T(n).
0 1 1 2 4 7 13 24 44 81 149 ...
Recursion without a cache is exponential, and here it is worse than for Fibonacci because each call spawns three.
Tabulation makes it one pass, and the point of putting it in this sub-topic is what happens next: the recurrence reaches back exactly three places, so only three values need to exist at any moment.
a, b, c = 0, 1, 1
repeat n - 2 times: a, b, c = b, c, a + b + c
That is O(1) space rather than O(n), and it is the same reduction as keeping two
variables for Fibonacci. The general rule is that a table can be collapsed to a
window as wide as the recurrence reaches.
The rotation must be simultaneous. Assigning a = b first and then b = c loses
the original b, and the sum comes out wrong from the very next term, so a
language without tuple assignment needs a temporary.
T(37) = 2082876103 is the largest term below 2^31, which is why the bound is 37
rather than a round number.
Constraints - `0 ≤ n ≤ 37` - The answer fits in a signed 32-bit integer.
Input
One line containing the integer n.
Output
Print one integer on a single line: the value of T(n), the nth term of the sequence.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.