Динамическое программирование
Динамическое программирование — это «искусство» построения некоторого состояния на основе предыдущих состояний. При выполнении вычислений нам часто нужны ранее найденные значения, вычисленные в ходе программы. Числа Фибоначчи — отличный пример, который можно вычислять при помощи динамического программирования:
Чтобы вычислить
fib(2), мы используем значения fib(1) и fib(0). В итоге получаем fib(2) = 1. Чтобы найти следующее число в последовательности Фибоначчи, нужно воспользоваться уже вычисленным значением: fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Аналогично, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 и fib(5) = fib(4) + fib(3) = 3 + 2 = 5. Последовательность продолжается таким же образом.На каждой итерации мы вычисляем текущее число Фибоначчи, опираясь на ранее полученные значения. Это можно реализовать с помощью списка:
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])Если задать
n = 5, программа выведет 5, а для n = 7 — 13.Суть динамического программирования как раз в том, что мы многократно вычисляем текущее состояние (в нашем случае текущее число Фибоначчи) на основе предыдущих состояний.
💡
Динамическое программирование — это метод, позволяющий строить текущее состояние на основе предыдущих состояний.
Задача — числа Трибоначчи
После того как вам наскучили числа Фибоначчи, вы решили перейти к числам Трибоначчи. Числа Трибоначчи определяются следующим образом:
Ваша задача — найти
n-е число Трибоначчи.Входные данные
На вход подаётся одно целое число
n (1 ≤ n ≤ 30).Выходные данные
Необходимо вывести
n-е число Трибоначчи.Примеры
Input | Output |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB