Динамическое программирование — это мощный метод в информатике и программировании, который позволяет нам решать сложные проблемы, разбивая их на более простые подзадачи. Эффективно решая и повторно используя эти подзадачи, мы можем оптимизировать наш код и найти оптимальное решение.

1. Мемоизация.
   Мемоизация — это метод, при котором мы сохраняем результаты дорогостоящих вызовов функций и повторно используем их, когда те же входные данные повторяются. Этот метод особенно полезен в рекурсивных алгоритмах. Давайте рассмотрим пример поиска n-го числа Фибоначчи:

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

2. Табуляция.
   Табуляция — это еще один подход в динамическом программировании, при котором мы создаем таблицу и заполняем ее итеративно, обычно снизу вверх. Этот подход полезен, когда мы можем определить порядок, в котором следует решать подзадачи. Давайте рассмотрим задачу поиска минимального количества шагов для достижения целевого числа:

def min_steps(n):
    table = [0] * (n + 1)
    for i in range(2, n + 1):
        table[i] = table[i - 1] + 1
        if i % 2 == 0:
            table[i] = min(table[i], table[i // 2] + 1)
        if i % 3 == 0:
            table[i] = min(table[i], table[i // 3] + 1)
    return table[n]

3. Задача о рюкзаке.
   Задача о рюкзаке — это классическая задача оптимизации, в которой нам дан набор предметов, каждый из которых имеет вес и ценность, и нам нужно определить максимальное значение, которое мы можем получить, выбрав подмножество предметы, которые укладываются в заданный лимит веса. Эту проблему можно эффективно решить с помощью динамического программирования. Вот упрощенная версия задачи о рюкзаке:

def knapsack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0

    if wt[n - 1] > W:
        return knapsack(W, wt, val, n - 1)

    return max(val[n - 1] + knapsack(W - wt[n - 1], wt, val, n - 1),
               knapsack(W, wt, val, n - 1))

Динамическое программирование — это фундаментальный метод, используемый в информатике и программировании для эффективного решения сложных задач. Разбивая проблемы на более мелкие подзадачи и повторно используя результаты, мы можем оптимизировать наш код и найти оптимальные решения. В этой статье мы исследовали различные методы, включая запоминание, табулирование и задачу о рюкзаке. Освоив эти методы, вы будете хорошо подготовлены к решению широкого спектра алгоритмических задач.