N-th Tribonacci Number in Java - Dynamic Programming | AskTheCode

N-th Tribonacci Number Solution | Dynamic Programming LeetCode | Ask The Code

---

Problem:

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

---

Sample Input:

4

Sample Output:

4

Explanation:

T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

---

Code:

class Solution {
    public int tribonacci(int n) {
        if (n <= 1) return n;
        if (n == 2) return 1;
        int[] trib = new int[n + 1];
        trib[0] = 0;
        trib[1] = 1;
        trib[2] = 1;
        for (int i = 3; i <= n; i++)
            trib[i] = trib[i - 3] + trib[i - 2] + trib[i - 1];
        return trib[n];
    }
}