N-th Tribonacci Number

Share

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).

Example 1
Input: n=4 → Output: 4
Example 2
Input: n=25 → Output: 1389537

Solution Approach

Iterative DP with three variables.

  • Base cases: T(0)=0, T(1)=1, T(2)=1.
  • For i from 3 to n: T = T0+T1+T2; shift variables.
Java
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 t=a+b+c;a=b;b=c;c=t;}
        return c;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)