All problems

N-th Tribonacci Number

Easy · dynamic programming

A sequence of whole numbers starts with 0, 1, 1. After that, every number is the sum of the three numbers right before it. So the sequence begins 0, 1, 1, 2, 4, 7, 13, 24, ....

Given an index n, return the number at position n, counting from position 0.

Examples

Example 1

Input: n = 4

Output: 4

The sequence is 0, 1, 1, 2, 4, so position 4 holds 4 (the sum of 1, 1 and 2).

Example 2

Input: n = 7

Output: 24

Positions 4, 5 and 6 hold 4, 7 and 13, and 4 + 7 + 13 = 24.

Example 3

Input: n = 1

Output: 1

Constraints

• 0 <= n <= 37
• The answer always fits in a 32-bit signed integer.