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])
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: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB