Динамическое программирование

Динамическое программирование – это подход к решению задач, при котором задача разбивается на ряд
перекрывающихся подзадач.

Решение каждой подзадачи сохраняется (мемоизация, кэширование) и используется по необходимости
в дальнейших задачах.

Важно, что оптимальным решением задачи считается объединение оптимальных
решений всех подзадач.

Ниже дается пример применения динамического программирования к задаче нахождения n-ного члена ряда Фибоначчи.

Чи́сла Фибона́ччи — элементы числовой последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

def fibonacci_dp_bottom_up(n):
    """
    Вычисляет n-й член ряда Фибоначчи с использованием динамического
    программирования (метод табулирования, снизу вверх).
    Сложность: O(n) по времени, O(n) по памяти.
    """
    if not isinstance(n, int) or n < 0:
        raise ValueError("N должно быть неотрицательным целым числом.")

    # 1. Обработка базовых случаев (подзадач)
    if n == 0:
        return 0
    if n == 1:
        return 1

    # 2. Инициализация таблицы (массива DP)
    # Создаем массив, где DP[i] будет хранить i-е число Фибоначчи.
    # Размер массива: n + 1 (индексы от 0 до n)
    dp_table = [0] * (n + 1)    # Возвращает список вида [0, 0, 0, ... 0, 0, 0]

    # Заполнение базовых, самых простых подзадач
    dp_table[1] = 1

    # 3. Решение перекрывающихся подзадач в цикле
    # Мы начинаем с F(2) и строим решение до F(n)
    for i in range(2, n + 1):
        # Оптимальное решение текущей подзадачи DP[i] строится
        # из оптимальных решений двух предыдущих подзадач.
        # Это исключает повторные вычисления, которые есть в наивной рекурсии.
        dp_table[i] = dp_table[i - 1] + dp_table[i - 2]

        # Вывод на печать для наглядности того, как данные сохраняются в массив
        print(dp_table)

    # 4. Возвращение финального ответа
    # n-е число Фибоначчи находится в последней ячейке таблицы.
    return dp_table[n]


# --- Примеры использования ---
n_value = 10
result = fibonacci_dp_bottom_up(n_value)

print(f"Число Фибоначчи F({n_value}) = {result}")  # F(10) = 55
# F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, F(8)=21, F(9)=34, F(10)=55