Dynamic Programming - N-th Tribonacci Number

The Tribonacci sequence is defined as T(0)=0, T(1)=1, T(2)=1, T(n+3)=T(n)+T(n+1)+T(n+2). Given n, return T(n).

Input: n=4 → Output: 4

Input: n=25 → Output: 1389537

Simple DP with three variables. No array needed.

Base: t0=0, t1=1, t2=1.
For i from 3 to n: next = t0+t1+t2; t0=t1; t1=t2; t2=next.
Return t2 (handle n=0 and n=1 separately).

class Solution { public int tribonacci(int n) { if (n == 0) return 0; if (n <= 2) return 1; int a = 0, b = 1, c = 1; for (int i = 3; i <= n; i++) { int next = a + b + c; a = b; b = c; c = next; } return c; } }

Time Complexity: O(N)
Space Complexity: O(1)