N-th Tribonacci Number
The Tribonacci sequence extends the Fibonacci concept by summing the three previous numbers instead of two. It is defined by T(0) = 0, T(1) = 1, T(2) = 1, and T(n) = T(n-1) + T(n-2) + T(n-3) for n >= 3.
Given an integer n, return the value of T(n).
Input & Output
Input
n — the index in the Tribonacci sequence
Output
the value of T(n)
Example
Input
n = 4
Output
4
Explanation
The sequence starts 0, 1, 1, 2, 4, so T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4.
Example
Input
n = 25
Output
1389537
Explanation
Applying the recurrence 23 more times past the three base cases reaches 1389537, which is why the values grow out of reach of a naive recursion quickly.
Constraints
0 <= n <= 37- the answer fits in a 32-bit integer