Динамическое программирование может быть одной из самых сложных концепций в изучении структур данных и алгоритмов не потому, что особенно трудно понять решения, написанные с использованием шаблонов динамического программирования, а потому, что очень трудно распознать проблему, которую можно решить с помощью динамического программирования. а затем выполнить решение. Как правило, одним из преимуществ решения DP является возможность написать рекурсивное решение. Однако не все рекурсивные задачи можно решить с помощью динамического программирования, поэтому существование рекурсивного решения не является идеальным подарком.
Есть два условия, которые должны быть выполнены в рекурсивном решении для использования динамического программирования: оптимальная подструктура и перекрывающиеся подзадачи. Чтобы изучить динамическое программирование, я хочу сначала объяснить, что означают эти условия и как узнать, выполняются ли они.
Оптимальная основа
Что означает, что задача имеет оптимальную подструктуру? Это означает, что оптимальное решение проблемы может быть найдено путем объединения оптимальных решений ее подзадач. Это часть динамического программирования, в которой рекурсия является подсказкой. Поскольку рекурсия по своей природе требует, чтобы решения подзадач объединялись для получения общего решения, рекурсивное решение является признаком того, что проблема имеет оптимальную подструктуру.
Примером задачи, подходящей под этот критерий, является последовательность Фибоначчи, которую я ранее рассмотрел как пример рекурсии. Поскольку n-е число последовательности Фибоначчи является суммой двух предыдущих чисел Фибоначчи, оно соответствует оптимальному ограничению подструктуры динамического программирования.
Перекрывающиеся подзадачи
Это ограничение проблем, которые могут быть решены с помощью динамического программирования, немного сложнее понять, чем оптимальную подструктуру. По сути, это означает, что, учитывая рекурсивное решение проблемы методом грубой силы, одни и те же подзадачи будут решаться неоднократно, поскольку общая функция генерирует окончательное решение. Это можно увидеть на диаграмме рекурсивного решения для n-го числа последовательности Фибоначчи выше: производящая функция решает fibo(4) дважды, fibo(3) трижды, fibo(2) пять раз и так далее (количество решений само по себе является функцией последовательности Фибоначчи).
Для более простой задачи, такой как шестое число последовательности Фибоначчи, эта рекурсия не требует слишком много времени для вычислений. Однако по мере того, как мы требуем все больших и больших чисел Фибоначчи, рекурсивное решение действительно начинает увеличивать вычислительную сложность. Эта задача имеет временную сложность — о которой я расскажу в одной из следующих статей этой серии, но о которой можно прочитать здесь и здесь — O(2^n), что считается крайне низкой производительностью. Динамическое программирование стремится устранить повторение перекрывающихся подзадач, решая каждую только один раз, тем самым устраняя высокую временную сложность многих рекурсивных решений.
Пример задачи
В оставшейся части статьи я буду демонстрировать динамическое программирование, используя следующую задачу (которую можно найти на Leetcode):
Получив массив
triangle, вернуть минимальную сумму путей сверху вниз. Для каждого шага вы можете перейти к соседнему номеру строки ниже. Более формально, если вы находитесь по индексуiв текущей строке, вы можете перейти либо к индексуi, либо к индексуi + 1в следующей строке.
Example 1: Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (bolded above). Example 2: Input: triangle = [[-10]] Output: -10
Очевидно, что это можно решить рекурсивно. Вот грубая сила или наивное рекурсивное решение. Если это будет отправлено на Leetcode, оно не будет пройдено, потому что превышает лимит времени, заданный количеством тестовых случаев. Однако его можно протестировать вручную, введя различные тестовые примеры в песочницу. Это работает.
var minimumTotal = function(triangle, idx = 0, height = 0) {
if(height === triangle.length - 1){
return triangle[height][idx]
}
let sum = 0;
let path1 = minimumTotal(triangle, idx, height + 1)
let path2 = minimumTotal(triangle, idx + 1, height + 1)
sum = triangle[height][idx] + Math.min(path1, path2)
return sum
}
Соответствует ли эта задача требованиям динамического программирования? Во-первых, имеет ли он оптимальную подструктуру? В силу того, что он запрашивает путь, мы можем сказать да — путь должен соединяться (быть в пределах определенного расстояния i или i + 1 от предыдущего числа) и путь должен проходить через полный треугольник (включать все строки массива). Следовательно, решения подзадач должны генерировать решение общей проблемы. Имеет оптимальную подструктуру.
Есть ли перекрывающиеся подзадачи в наивном рекурсивном решении? В этом случае ответ прост: «да». Если мы изучим код в приведенном выше фрагменте, то ясно увидим, что каждый запуск функции пересчитывает путь1 и путь2, и этот путь1 для одного числа будет таким же, как path2 для предыдущего номера и так далее. Существует довольно много совпадений.
Поскольку задача удовлетворяет условиям для переработки с помощью динамического программирования, теперь мы можем рассказать, как изменить рекурсивное решение так, чтобы подзадачи решались только один раз, что экономит много времени на решение.
Динамическое программирование через табуляцию
Есть два основных метода, которые можно использовать для уменьшения сложности рекурсивных решений: запоминание и табулирование. Мемоизацию можно рассматривать как «нисходящий» подход к решению рекурсивной задачи. Хотя он сохраняет часть рекурсии в исходном решении, он передает решения предыдущих подзадач вниз по рекурсии до тех пор, пока не будет построено решение. Хотя это экономит время по сравнению с чистой рекурсией, многие инженеры считают его отличным от реального динамического программирования. Обычный метод динамического программирования, называемый табулированием, работает почти противоположным образом. Вместо того, чтобы работать сверху вниз, табулирование работает в обратном направлении, двигаясь снизу вверх в проблеме. В случае треугольного массива в этой задаче табличное решение буквально работает от основания треугольника к вершине.
Вот пример табличного решения задачи о минимальной сумме массива треугольников, описанной выше:
var minimumTotal = function(triangle) {
for(let row = triangle.length - 2; row >= 0; row--){
for(let col = 0; col < triangle[row].length; col++){
triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1])
}
}
return triangle[0][0]
};
Это довольно умное решение (за которое я не беру кредит — оно принадлежит ChippyChoppy, также известному как моя подруга Бекка) использует сам массив треугольников для хранения множества основанных на путях решений до тех пор, пока не будет достигнута вершина треугольника. Начиная со строки чуть выше нижнего (предпоследнего подмассива треугольного массива), функция добавляет меньший из двух путей ниже к текущему числу в массиве. Затем он переходит к следующей строке, выполняя то же действие, пока не вернет верхнее число треугольника, которое теперь является минимальной суммой пути. Следующий псевдокод немного яснее показывает, что происходит:
// Test array: [[2],[3,4],[6,5,7],[4,1,8,3]] // Starting on the [6,5,7] row, we add the smaller of the two // numbers below each to that number // [6,5,7] becomes [6+1,5+1,7+3] or [7,6,10] // Moving up to the [3,4] row we do the same // [3,4] becomes [3+6,4+6] or [9,10] // And now we add to the 'top' or zeroth row // [2] becomes [2+9] or 11 // return the top row, only number, which is now the sum, 11
В отличие от рекурсивного решения 2 ^ n, сложного по времени, это решение динамического программирования с помощью табуляции имеет временную сложность всего O (n²), потому что оно проходит через вложенную пару циклов для полного размера входного набора данных (n) .
Хотя это, безусловно, не полный обзор всех проблем, которые можно решить с помощью динамического программирования, и не всех задействованных методов, я, безусловно, надеюсь, что это полезное введение в тему. Динамическое программирование — отличный способ уменьшить временную сложность задач, которые можно решить с помощью грубой силы с использованием рекурсии.
