N-th Tribonacci Number
Easy· 1D DP
Problem
The Tribonacci sequence starts with T0 = 0, T1 = 1, T2 = 1, and every later term is the sum of the three terms before it. Given n, return Tn.
Examples
Input: n = 4
Output: 4
T3 = 0+1+1 = 2, T4 = 1+1+2 = 4.
Input: n = 10
Output: 149
Constraints
- • 0 <= n <= 37
- • The answer fits in a 32-bit integer.
Hints & approach
Hint 1
Naive recursion recomputes the same terms many times.
Hint 2
Build the terms bottom-up from the three known base values.
Hint 3
Only the last three terms are ever needed.
Approachtry the hints first
This is the simplest possible DP: the state is the index, the transition is T[i] = T[i-1] + T[i-2] + T[i-3], and the base cases are given. Iterate from 3 to n keeping three rolling variables and shift them each step. It is a good warm-up for recognising that memoising a recurrence turns exponential recursion into linear work.
Time O(n) · Space O(1)