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] = 0, fib[1] = 1

for i in range(2, n + 1):
    fib.append(fib[i - 1] + fib[i - 2])
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.


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


The output should contain the n-th Tribonacci number.




Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue