5.1 Определение динамического программирования
Динамическое программирование (Dynamic Programming, DP) — это метод оптимизации, который используется для решения сложных задач путём разбиения их на более простые подзадачи. Динамическое программирование эффективно используется для задач, которые можно разбить на перекрывающиеся подзадачи с оптимальной структурой подзадач.
Принципы работы:
1. Оптимальная подструктура:
Задача обладает оптимальной подструктурой, если её оптимальное решение можно построить из оптимальных решений её подзадач. Это означает, что можно решить большую задачу, решив несколько меньших подзадач.
2. Перекрывающиеся подзадачи:
Задача имеет перекрывающиеся подзадачи, если её подзадачи повторяются несколько раз в процессе решения задачи. Динамическое программирование эффективно решает задачи с перекрывающимися подзадачами путём запоминания результатов уже решённых подзадач (мемоизация).
3. Мемоизация и табуляция:
Мемоизация (сверху вниз): Рекурсивный подход, при котором результаты подзадач сохраняются в памяти для избежания повторных вычислений.
Табуляция (снизу вверх): Итеративный подход, при котором результаты подзадач вычисляются и сохраняются в таблице (обычно массиве) и используются для вычисления конечного результата.
Примеры задач, решаемых методом динамического программирования
5.2 Задача о рюкзаке
Задача:
Имеется набор предметов, каждый с весом и стоимостью. Нужно выбрать предметы для рюкзака с ограниченной грузоподъемностью, чтобы максимизировать общую стоимость.
Важно! В отличии от аналогичной задачи, которая хорошо решалась жадным алгоритмом, в этой задаче дробить предметы нельзя.
Решение:
Создается таблица, где строки соответствуют предметам, а столбцы — возможной вместимости рюкзака. Значение в ячейке представляет максимальную стоимость для данного числа предметов и вместимости.
Временная сложность: O(n * W), где n — количество предметов, W — вместимость рюкзака.
Пример кода на Python:
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
5.3 Задача о нахождении наименьшего пути
Задача:
Найти кратчайшие пути между всеми парами вершин взвешенного графа.
Решение:
Используется таблица, где строки и столбцы соответствуют вершинам графа. Значение в ячейке представляет кратчайшее расстояние между двумя вершинами.
Временная сложность: O(V^3), где V — количество вершин
Пример кода на Python:
def floyd_warshall(graph):
v = len(graph)
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
for k in range(v):
for i in range(v):
for j in range(v):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
5.4 Сравнение динамического программирования с другими методами
Сравнение с методом грубой силы (brute force):
Временная сложность:
- Грубая сила: часто имеет экспоненциальную временную сложность (например,
O(2^n)для задачи Фибоначчи). - Динамическое программирование: уменьшает временную сложность до полиномиальной (например,
O(n)для задачи Фибоначчи).
Пространственная сложность:
- Грубая сила: может использовать меньше памяти, но временные затраты высоки.
- Динамическое программирование: может использовать больше памяти для хранения промежуточных результатов (например,
O(n)для задачи Фибоначчи с мемоизацией), но выигрывает во времени.
Сравнение с методом жадных алгоритмов (greedy algorithms):
Оптимальность:
- Жадные алгоритмы: не всегда находят глобально оптимальное решение, но работают быстрее и проще в реализации.
- Динамическое программирование: находит глобально оптимальное решение, но требует больше вычислительных ресурсов.
Примеры задач:
- Жадные алгоритмы: задача о рюкзаке с дробями (fractional knapsack), минимальное остовное дерево (MST).
- Динамическое программирование: задача о рюкзаке (целочисленная), наибольшая общая подпоследовательность (LCS).
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ