Понимание механизма Фибоначчи в динамическом программировании 1D
Динамическое программирование (DP) может быть пугающей темой для изучения. Плюс-минус, я организовал заметки по теме предыдущих изменений работы в виде удобоваримого руководства для более быстрого ввода в эксплуатацию. Меньше математики, больше лженауки.
На высоком уровне динамическое программирование следует аналогичной стратегии по всем направлениям:
- Разбейте сложную проблему на более простые подзадачи
- Находит оптимальное решение подзадач
- Сохранение результатов подзадач (запоминание)
- Используйте их повторно, чтобы не рассчитывался один и тот же набор подзадач.
- Наконец вычислить результаты сложной задачи
Понимание механики одномерного динамического программирования
Сегодня мы познакомимся с этим механизмом для 1D DP, сначала тщательно изучив одну проблему с буквенным кодом, 53. Максимальный подмассив. Затем мы сравниваем упрощенные формы 1D DP, которые легко запомнить и применять позже в более сложных задачах.
Не нужно переходить на сайт, провоцирующий режим «бей или беги» — проблема описана ниже:
Problem Description Given an integer array nums, find the subarray which has the largest sum and return its sum. Example: Input: nums = [5, 4, -10, 7, 8] Output: 15 Explanation: [7, 8] has the largest sum = 15.
Ключом к распознаванию проблем DP является поиск шаблонов/ключевых слов в письменных задачах, т. е. перекрывающихся подзадач, непрерывных подмассивов, максимальных/минимальных значений результата и т. д.
Следующие слова выделены в задаче, чтобы указать на возможность выполнения алгоритма одномерного динамического программирования:
- подмассив — непрерывные вычисления позволяют выполнять сравнительную итерацию, которая сама по себе определяет «текущее» агрегированное значение подмассива. Вот как DP может уменьшить потребность в повторных вычислениях: он получает доступ к сохраненным данным через некоторую структуру, которую вы вызвали сами, или сам стек вызовов.
- наибольшая сумма —условие каждого сравнения.
- возвратить его сумму —поскольку нам нужно вернуть результат агрегированного массива, это означает, что нам нужно всегда отслеживать вычисляемое число.
В реальную задачу включены дополнительные наборы примеров, полезные для тестирования пограничных случаев: для ясности и краткости мы работаем с более приемлемым набором чисел, чтобы лучше проиллюстрировать механизм алгоритма, который мы придумали вместе.
Почему ДП крутой?
При правильных условиях динамическое программирование позволяет нам экспоненциально сократить объем вычислений, имея при этом решение только для первых двух чисел набора, f(0) и f(1).
Когда мы находим f(0) и f(1), мы можем выполнить дополнительные вычисления с тем, что уже было рассчитано, чтобы уменьшить количество повторных вычислений.
Чтобы лучше понять, как это может работать, давайте рассмотрим метод грубой силы для оценки ввода nums = [5, 4, -10, 7, 8]. Сначала сравнивается максимальная сумма при длине подмассива 1, где к концу первой итерации 8 сохраняется как текущий максимум. Затем выполняется еще одна итерация для подмассива длины 2, такого как [5,4], [4, -10] и т. д.
Каждая итерация увеличивала длину подмассива до максимальной длины, оставляя амортизированную O (2 ^ n) временной сложности. Возможно, вы могли заметить, что определенные наборы вычислений повторяются без необходимости, например, необходимость повторять вычисление суммы подмассива [4, -10] в более крупных подмассивах, таких как [5, 4, -10], [4, -10, 7], [5, 4, -10, 7], [5, 4, -10, 7] и [5, 4, -10, 7, 2]. Этот шаблон можно описать как грубая рекурсия.
Рекурсия грубой силы
Временная сложность: O(2^n) | Сложность пространства: O(n)
fun recursionFib(n: Int): Int {
if (n <= 1) return n
return recursionFib(n - 1) + recursionFib(n - 2)
}
Именно здесь динамическое программирование действительно сияет, потому что его алгоритмы сохраняют уже вычисленные результаты. Давайте снова вернемся к задаче о максимальной сумме подмассива:
Problem Description Given an integer array nums, find the subarray which has the largest sum and return its sum. Example: Input: nums = [5, 4, -10, 7, 8] Output: 15 Explanation: [7, 8] has the largest sum = 15.
Для DP необходимы только первые два вычисления — f(0) базовый случай и f(1) условный. Эти два вычисления определят, как будут вычисляться остальные функции.
Стратегия, которую мы используем, называется алгоритм Кадане, где max\min совокупности текущего непрерывного значения сохраняется для отслеживания.
Базовый случай — nums[0] (при условии, что массив непуст). Мы сохраняем это значение в таблице результатов dp, чтобы отслеживать его как значение currMax. Теперь мы смотрим на следующее значение в nums и спрашиваем себя, 4 больше, чем 4 + 5? Это не так, поэтому мы сохраняем сумму nums[0] + nums[1] в dp[1].
dp[0] = nums[0] dp[1] = maxOf(dp[0]+nums[1], nums[1] ) // maxOf( 5+4, 4) dp[1] = 9
Если мы применим ту же логику к третьему индексу, мы оценим:
dp[2] = maxOf(dp[1]+nums[2], nums[2] ) // maxOf( 9 - 10, -10) dp[2] = -1
dp[2] теперь равно -1, что меньше dp[1] означает, что непрерывный подмассив достиг своего возможного максимума.
Вот и все, мы разобрались с механизмом. Мы можем использовать эту формулу для расчета каждого совокупного индекса после.
dp[i] = maxOf(dp[i-1]+nums[i], nums[i] )
С помощью динамического программирования мы можем выполнить итерацию по массиву только один раз в течение скудного, амортизированного времени O (n) и сохранить уже вычисленные результаты, поэтому нет необходимости повторять уже вычисленные значения при итерации по массиву.
На самом деле нам не нужно хранить эти результаты в другой таблице. Мы могли бы просто использовать существующий nums для хранения результатов, так как нам нужно двигаться вперед только один раз, и нам нужен только maxSum , в то время как все остальные «текущие максимальные суммы» хранятся в каждом индексе.
fun maxSubArray(nums: IntArray): Int {
if (nums.isEmpty()) return 0
if (nums.size == 1) return nums[0]
var maxSum = nums[0]
(1 until nums.size).forEach { i ->
nums[i] = maxOf(nums[i], nums[i] + nums[i-1])
maxSum = maxOf(nums[i], maxSum)
}
return maxSum
}
Теперь, когда мы рассмотрели, как создать алгоритм для одномерной задачи DP, мы обратимся к краткому руководству по сравнительным формам одномерного динамического программирования, которые могут лучше соответствовать определенным условиям для задачи.
Табуляция (снизу вверх)
Временная сложность: O(n) | Сложность пространства: O(n)
Если все подзадачи должны быть решены по крайней мере один раз, восходящий алгоритм обычно превосходит нисходящий алгоритм запоминания. Это аналогичная форма, которую мы использовали в нашем предыдущем примере!
fun tabulationBottomUp(n: Int): Int {
if (n <= 1) return n
val dp = IntArray(n + 1) { 0 }
dp[1] = 1
(2..n).forEach { i ->
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
Мемоизация (сверху вниз)
Временная сложность: O(n) | Сложность пространства: O(n)
Мемоизация лучше, когда все подзадачи нужно решить сразу.
fun memoizationTopDownFib(n: Int): Int {
if (n <= 1) return n
val dp = IntArray(n) { n }
if (dp[n] != 0) return n
dp[n] = memoizationTopDownFib(n - 1) + memoizationTopDownFib(n - 2)
return dp[n]
}
Оптимизировано по пространству
Временная сложность: O(n) | Сложность пространства: O(1)
fun spaceOptimization(n: Int): Int {
if (n <= 1) return n
var one = 1
var two = 0
(0 until n).forEach { i ->
tmp = one
one += two
two = tmp
}
return one
}
Дополнительные ресурсы
Эта информация была собрана в результате многочасового просмотра ресурсов YouTube и других полезных статей. Я настоятельно рекомендую углубиться в эти наборы задач, так как многие люди находят отличные способы объяснить эту концепцию каждый раз немного по-новому. Каждый из этих людей заслуживает медали за глубокие знания по этому вопросу.
