Основы динамического программирования для решения алгоритмических задач

Рисунок: основы динамического программирования

Введение

Динамического программирование (Dynamic Programming, DP) - один из используемых подходов при решении алгоритмических задач. Он эффективен в задачах, где оптимальное решение можно построить из оптимальных решений подзадач.

В этой статье мы разберемся, что такое динамическое программирование, как его применять.

Что такое динамическое программирование?

Динамическое программирование (DP) - это метод оптимизации, при котором сложная задача разбивается на более простые перекрывающиеся подзадачи, и их решения запоминаются, чтобы не пересчитывать их снова.

Основные признаки задачи на динамическое программирование DP:

1. Перекрывающиеся подзадачи — одна и та же подзадача решается многократно.
2. Оптимальная подструктура — оптимальное решение задачи зависит от оптимальных решений её подзадач.

Два подхода к DP:

• Мемоизация — рекурсия с кэшированием результатов.
• Табуляция — итеративное заполнение таблицы снизу вверх.

Пример 1: Числа Фибоначчи

Найти n-е число Фибоначчи:

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2)

Наивное решение (рекурсия без оптимизации):

Рисунок: листинг расчет числа Фибоначчи с использованием рекурсии, без сохранения промежуточного результата

Проблема: экспоненциальное время из-за повторных вычислений.

Решение 1: Мемоизация

Рисунок: листинг решения задачи Фибоначчи методом мемоизации

Решение 2: Табуляция

Рисунок: листинг решения задачи Фибоначчи методом Табуляции

Оптимизация до O(1) памяти:

Рисунок: листинг решения задачи Фибоначчи оптимизированным методом

Пример 2: Задача о рюкзаке

Задача

У вас есть рюкзак, который выдерживает вес W, и набор предметов. Каждый предмет имеет вес weight[i] и стоимость value[i]. Вы можете взять каждый предмет не более одного раза. Нужно максимизировать стоимость, не превысив вес.

Подход

Используем DP: dp[i][w] — максимальная стоимость, которую можно получить, используя первые i предметов и вес не более w.

Рисунок: листинг метода knapsack

Рисунок: листинг метода main

Как работает:

• dp[i][w] — лучшая стоимость для первых i предметов и веса w.
• На каждом шаге решаем: взять предмет или нет?
• Ответ: dp[n][W].

Когда применять динамическое программирование?

Используйте DP, если:

• Задача требует поиска оптимума (максимум, минимум).
• Есть перекрывающиеся подзадачи.
• Можно выразить решение через решения подзадач.

Советы по решению задач на DP

1. Определите состояние: что хранит dp[i] или dp[i][j]?
2. Найдите рекуррентное соотношение: как текущее состояние зависит от предыдущих?
3. Определите базовые случаи.
4. Выберите подход: мемоизация или табуляция.
5. Оптимизируйте память, если возможно.

Заключение

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

Начните с простых задач (Фибоначчи, рюкзак), постепенно переходите к более сложным.

Листинги примеров, рассмотренных в статье можно найти по адресу:

https://github.com/ShkrylAndrei/blog_yandex/tree/main/src/main/java/info/algorithms/dp