#1137
N-th Tribonacci Number
Easy 1D DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
T0 = 0, T1 = 1, T2 = 1 and each later term is the sum of the three before it. Return Tn.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: each term is the sum of the previous three.
Why this works: keep the last three values and roll forward.
Example: 0, 1, 1, 2, 4, 7 → T5 = 7
✦Hints open one at a time
Same idea as Fibonacci with three previous values.
Memoised recursion and the iterative loop give the same O(n).
↗Approach
Roll three variables forward n − 2 times.
</>Solution (Java)
class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n < 3) return 1;
int a = 0, b = 1, c = 1;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b;
b = c;
c = d;
}
return c;
}
}!Common mistake
Forgetting the base cases for n = 0, 1 and 2.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon