# Nth Tribonacci Number

Let's solve the Nth Tribonacci Number problem using Dynamic Programming.

## Statement

Tribonacci numbers are a sequence of numbers where each number is the sum of the three preceding numbers. Your task is to find the $n^{th}$ Tribonacci number.

The Tribonacci sequence is defined as:

$T_0 = 0,\space T_1 = 1,\space T_2 = 1$, and $\space T_n = T_{n-1} + T_{n-2} + T_{n-3}, \space$ for $n >= 3$ |
---|

The input number, `n`

, is a non-negative integer.

Let’s say you have to find the fifth Tribonacci number in the sequence. From the sequence defined above, we know that $T_0 = 0, T_1 = 1, T_2 = 1$. The sequence will be:

$0, 1, 1, 2, 4, 7$

Therefore, the fifth term will be 7.

**Constraints:**

- $0 \leq$
`n`

$\leq 73$ - The answer is guaranteed to fit within a 64-bit integer, i.e., answer $\leq 2 ^{63} - 1$

## Examples

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.