Algorithms and Data Structures

# Dynamic Programming

Dynamic programming is the “art” of constructing a certain state based on the previous states. When doing computations, we often rely on the previous values calculated during the execution. Fibonacci numbers are a great example that can be calculated using dynamic programming:
So, to calculate fib(2) we would use the values fib(1) and fib(0). Therefore, obtaining the value for fib(2) = 1. To get the next value in the Fibonacci sequence, we should make use of the value we calculated previously - fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Similarly, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 and fib(5) = fib(4) + fib(3) = 3 + 2 = 5, and the sequence goes on.
On each iteration, we calculate the current value of the Fibonacci sequence using the previous states that we calculated beforehand. This can be implemented with a list:
n = ...
fib = [0, 1]       # fib = 0, fib = 1

for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])
For a value n = 5, the program would print 5, while for a value n = 7 it would print 13.
The process of repeatedly calculating the current state (the current Fibonacci number in our case) using the previous states is the essence of Dynamic Programming.

💡
Dynamic programming is a technique to construct the current state based on the previous states.

### Challenge - Tribonacci numbers

After playing with Fibonacci numbers, you got bored and decided to play with Tribonacci numbers instead. Tribonacci numbers are defined as:
Your task is to find the n-th Tribonacci number.

#### Input

The input contains a single integer n (1 ≤ n ≤ 30).

#### Output

The output should contain the n-th Tribonacci number.

#### Examples

 Input Output 2 1 4 2

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB