N-th Tribonacci Number

Given n, return the n-th Tribonacci number where T(0)=0, T(1)=1, T(2)=1, and T(n)=T(n-1)+T(n-2)+T(n-3). Pattern focus: Linear Recurrence DP. This extends Fibonacci to three previous states.

Input Format

n = Tribonacci index

Output Format

the n-th Tribonacci number

Constraints

  • 0 <= n <= 37

Examples

Example 1:

Input:

n = 4

Output:

4

Explanation:

The sequence begins 0,1,1,2,4.

Example 2:

Input:

n = 5

Output:

7

Explanation:

T(5) = 4 + 2 + 1 = 7.

Loading...
N-th Tribonacci Number - Dp 1d DSA Problem