easyDynamic Programming 1DPure DSA~11 min
Tribonacci Capacity Forecast
A capacity model forecasts the next period as the sum of the previous three observed periods. Given the index n, return the n-th value of this Tribonacci sequence.
Problem
The Tribonacci sequence is defined by T0 = 0, T1 = 1, T2 = 1, and Tn = Tn−1 + Tn−2 + Tn−3 for n ≥ 3. Given n, return Tn.
Input
An integer n (0 ≤ n ≤ 37, fits in 32-bit).
Output
An integer — the n-th Tribonacci number.
Constraints
- T0=0, T1=1, T2=1
- 0 ≤ n ≤ 37
- Answer fits in a 32-bit signed integer
Examples
Example 1
Input
n = 4
Output
4
T3 = 0+1+1 = 2, T4 = 1+1+2 = 4.
Example 2
Input
n = 25
Output
1389537
Following the recurrence to index 25.