600. N-th Tribonacci Number
The tribonacci sequence is the Fibonacci idea with a three-term memory. It is seeded with T(0) = 0, T(1) = 1, T(2) = 1, and every later term is the sum of the three terms just before it:
T(n + 3) = T(n) + T(n + 1) + T(n + 2)
Your function receives a single integer n and returns the value of T(n).
Example 1:
Input: n = 4
Output: 4
Explanation: T(3) = 0 + 1 + 1 = 2, then T(4) = 1 + 1 + 2 = 4.
Example 2:
Input: n = 25
Output: 1389537
Explanation: Chaining the recurrence 23 more times from the seeds reaches T(25) = 1389537.
Constraints:
- 0 ≤ n ≤ 37
- The answer fits in a signed 32-bit integer (T(37) = 2082876103).
Hints:
Writing `t(n) = t(n-1) + t(n-2) + t(n-3)` directly as recursion recomputes the same values an exponential number of times. What could you remember to visit each value only once?
Build the sequence forward from the seeds instead. To produce the next term you only ever look at the last three — so three variables that slide forward are all the state you need.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4
Expected output: 4