Сяохао: Осадный лев из Технологического центра Исинь. Он любит алгоритмы и обучение. Он не ограничивается скучными кодами программирования. Он предпочитает кратко объяснять проблему в непринужденной форме.
Динамическое программирование, серия 1: Восхождение по лестнице
1.1 Объяснение концепции
Существует много материалов, объясняющих динамическое программирование, официальное определение относится к преобразованию многоэтапного процесса в ряд одноэтапных задач и решению их по очереди с использованием связи между каждым этапом. Соотношение между стадиями в концепции фактически относится к уравнению перехода состояния. Многие думают, что ДП сложен (далее в совокупности именуемые динамическим программированием как ДП).Фундаментальная причина заключается в том, что ДП отличается от некоторых алгоритмов фиксированной формы (таких как DFS, дихотомия, KMP), и нет реальных шагов для указать, что делать на первом шаге и втором шаге. , так что, если быть точным, DP на самом деле является идеей решения проблем.
Суть этой идеи такова: относительно крупномасштабная задача (задача, которую можно представить двумя-тремя параметрами) может быть получена по результатам нескольких задач меньшего масштаба (обычно ищется какая-то особая логика вычислений, например найти максимальное значение и др.)
Таким образом, уравнения перехода состояний, которые мы обычно видим, в основном такие:
opt : Относится к специальной логике расчета, обычно max или min.
i,j,k — все параметры, используемые при определении уравнения ДП.
Каждое уравнение перехода состояния имеет некоторые тонкие отличия. На самом деле это очень легко понять: в мире так много взаимосвязей, что невозможно абстрагироваться от формулы, которую можно было бы применить полностью. Так что лично я не рекомендую заучивать наизусть различные типы уравнений перехода состояний. Но тип вопроса DP действительно совершенно невозможно понять и не может быть классифицирован для анализа? Я так не думаю. В этой серии я раскрою тему динамического программирования от простого к сложному.
Давайте сначала рассмотрим простейшую тему DP и познакомимся с концепцией DP:
Вопрос: Предположим, вы поднимаетесь по лестнице. Вам нужно n шагов, чтобы добраться до вершины здания. Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания? Примечание. Данное n является положительным целым числом.
Пример 1:
Ввод: 2 Выход: 2 Пояснение: Есть два способа подняться на вершину здания.
Уровень 1 + Уровень 1
Уровень 2
Пример 2:
Ввод: 3 Выход: 3 Пояснение: Есть три способа подняться на вершину здания.
Уровень 1 + Уровень 1 + Уровень 1
Уровень 1 + Уровень 2
Уровень 2 + Уровень 1
1.2 Диаграмма вопроса
Путем анализа мы можем прояснить, что проблема может быть разложена на некоторые подзадачи, содержащие оптимальные подзадачи, то есть ее оптимальное решение может быть эффективно построено из оптимальных решений ее подзадач.удовлетворить"разбить большую проблему на несколько более мелких проблем"**. Итак, пусть dp[n] обозначает общее количество методов, которые могут достичь n-го порядка, и можно получить следующее уравнение перехода состояния:
dp[n]=dp[n-1]+dp[n-2]
Поднимитесь на 1 ступеньку: есть 1 способ.
На 2 шага вверх: есть 1+1 и 2 пути.
На 3 шага вверх: общее количество методов для достижения 3 равно сумме количества методов до 1 и 2.
Поднимаясь вверх по n шагам, общее количество методов для достижения n-го шага равно сумме количества методов для (n-1)-го и (n-2)-го шагов.
1.3 Пример языка Go
Согласно анализу полученный код выглядит следующим образом:
func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
Динамическое программирование, серия II: максимальная сумма подзаказов
2.1 Максимальная сумма подзаказа
Вопрос: Учитывая целочисленный массив nums, найдите непрерывный подмассив с наибольшей суммой (подмассив содержит хотя бы один элемент) и верните его наибольшую сумму.
Пример :
Ввод: [-2,1,-3,4,-1,2,1,-5,4],
Выход: 6
Объяснение: максимальная сумма последовательных подмассивов [4,-1,2,1] равна 6.
Когда вы получите вопрос, пожалуйста, не смотрите на решение ниже, сначала подумайте об этом 2-3 минуты...
2.2 Диаграмма вопроса
Первым делом разбираем задачу, непрерывный подмассив должен заканчиваться числом, тогда можно определить состояние следующим образом:
dp[i]: представляет максимальную сумму смежных подмассивов, оканчивающихся на nums[i].
Так почему же оно так определено? Потому что это определение на самом деле проще всего придумать! В предыдущем разделе мы упомянули, что уравнение перехода состояния на самом деле представляет собой уравнение с 1-3 параметрами, описывающее взаимосвязь между мелкомасштабными и крупномасштабными проблемами.
Конечно, если вы не думали об этом, это на самом деле вполне нормально! Потому что «задача была впервые поставлена в 1977 году, но оптимальное решение за линейное время не было найдено до 1984 года».
Согласно определению состояния приступим к анализу:
Если вы хотите получить dp[i], то необходимо выбрать nums[i]. И непрерывная подпоследовательность, представленная dp[i] и непрерывная подпоследовательность, представленная dp[i-1], скорее всего, будут отличаться на один nums[i] . который
dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0)
Но тут у нас проблема, ** весьма вероятно, что dp[i-1] само по себе является отрицательным числом. В этом случае, если dp[i] получается из dp[i-1]+nums[i], то результат на самом деле становится меньше, потому что dp[i] требует максимальной суммы. ** Так что в этом случае, если dp[i-1]
dp[i] = nums[i] , if (dp[i-1] < 0)
Из приведенного выше анализа мы можем получить:
dp[i]=max(числа[i], dp[i−1]+числа[i])
Уравнение перехода состояния получено, но нам также нужно вывести его из существующего состояния.Мы можем думать, что **dp[0] должно заканчиваться на nums[0], **so
dp[0] = nums[0]
Во многих вопросах, поскольку сам dp[i] определяется как вопрос в заголовке, dp[i] в конечном итоге является ответом. Однако определение состояния здесь не проблема в заголовке, и он не может напрямую вернуться в последнее состояние (новички часто падают на этом шаге). Итак, окончательный ответ, собственно, и ищем:
max(dp[0], dp[1], ..., d[i-1], dp[i])
После анализа строим график:
Предположим, что числа равны [-2,1,-3,4,-1,2,1,-5,4]
2.3 Пример языка Go
Согласно анализу полученный код выглядит следующим образом:
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
//设置初始化值
dp[0] = nums[0]
for i := 1; i < len(nums); i++ {
//处理 dp[i-1] < 0 的情况
if dp[i-1] < 0 {
dp[i] = nums[i]
} else {
dp[i] = dp[i-1] + nums[i]
}
}
result := -1 << 31
for _, k := range dp {
result = max(result, k)
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Мы можем еще больше упростить код:
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
result := nums[0]
dp[0] = nums[0]
for i := 1; i < len(nums); i++ {
dp[i] = max(dp[i-1]+nums[i], nums[i])
result = max(dp[i], result)
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Анализ сложности: временная сложность: O(N). Пространственная сложность: O(N).
Третья серия динамического программирования: самая длинная восходящая последовательность
3.1 Самая длинная восходящая подпоследовательность
Вопрос: Дан неупорядоченный массив целых чисел. Найдите в нем длину самой длинной возрастающей подпоследовательности.
Пример:
Ввод: [10,9,2,5,3,7,101,18]
Выход: 4
Объяснение: самая длинная восходящая подпоследовательность — [2,3,7,101], и ее длина равна 4.
Объяснение: Может быть несколько комбинаций самой длинной восходящей подпоследовательности, вам нужно только вывести соответствующую длину.
Этот вопрос имеет некоторую сложность!
Если вы понятия не имеете, ознакомьтесь с учебным содержанием предыдущей статьи!
Не рекомендуется читать решение напрямую!
3.2 Диаграмма вопроса
Первым делом разбираем задачу, ищем самую длинную возрастающую подпоследовательность (Longest Increasing Subsequence, LIS). Поскольку заглавие не требует непрерывности, ЛИС может быть непрерывной или прерывистой. В то же время ЛИС удовлетворяет условию, что она может быть построена из оптимального решения своих подзадач. Поэтому мы можем попытаться решить ее с помощью динамического программирования. Сначала определим состояние:
dp[i] : указывает длину самой длинной восходящей подпоследовательности, заканчивающейся на nums[i]
Мы предполагаем, что числа равны [1, 9, 5, 9, 3]
Обсуждаем в двух случаях:
Если nums[i] меньше всех предыдущих элементов, то dp[i] равно 1 (то есть самому себе) (этот вывод правильный)
Если перед nums[i] стоит элемент nums[j] меньше его, то dp[i] равно dp[j]+1** (этот вывод неверен, например nums[3]>nums [0], то есть 9 >1, но dp[3] не равно dp[0]+1)**
Мы сначала пришли к вышеуказанным выводам, но обнаружили некоторые проблемы. Потому что не обязательно есть только один элемент перед dp[i], который меньше его!
Возможно, помимо nums[j], также nums[k], nums[p] и так далее. Таким образом, dp[i] может быть равно dp[k]+1, dp[p]+1 и так далее, в дополнение к тому, что оно равно dp[j]+1. Итак, мы хотим найти dp[i], нам нужно найти максимум dp[j]+1, dp[k]+1, dp[p]+1 и так далее. (Я выделил жирным шрифтом все 3 бла-бла-бла, в основном потому, что новичкам очень легко кувыркаться здесь! Цель выделения здесь - запомнить этот тип вопроса!)
который:
dp[i] = max(dp[j]+1, dp[k]+1, dp[p]+1, .....)
Просто удовлетворить:
nums[i] > nums[j]
nums[i] > nums[k]
nums[i] > nums[p]
....
В конце концов, нам просто нужно найти максимальное значение в массиве dp, что и является ответом, который мы ищем.
После анализа строим график:
3.3 Пример языка Go
Согласно анализу полученный код выглядит следующим образом:
func lengthOfLIS(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
result := 1
for i := 0; i < len(nums); i++ {
dp[i] = 1
for j := 0; j < i; j++ {
//这行代码就是上文中那个 等等等等
if nums[j] < nums[i] {
dp[i] = max(dp[j]+1, dp[i])
}
}
result = max(result, dp[i])
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Серия динамического программирования 4: треугольная минимальная сумма пути
В предыдущих главах мы изучили метод анализа DP (динамическое программирование) в линейных отношениях через темы «Самая длинная возрастающая подпоследовательность» и «Максимальная сумма подпоследовательности». Этот метод анализа, также известный как «линейное динамическое программирование» в исследовании операций, конкретно относится к «целевой функции — это линейная функция конкретных переменных, а ограничения — линейные неравенства или уравнения этих переменных, и цель состоит в том, чтобы найти целевая функция. максимум или минимум». Этого пункта достаточно для понимания всеми, не нужно его запоминать, не говоря уже о том, чтобы имитировать!
В этом разделе мы продолжим анализ типа вопроса, который немного отличается от предыдущего.Мы надеемся, что этот вопрос можно будет сравнить и продемонстрировать с предыдущим, а затем успешно решить!
4.1 Треугольная сумма минимального пути
Вопрос: Для данного треугольника найдите минимальную сумму путей сверху вниз.
Пример:
Каждый шаг может перемещаться только к соседним узлам в следующей строке.
Например, для треугольника:
Минимальная сумма путей сверху вниз равна 11 (т. е. 2 + 3 + 5 + 1 = 11).
4.2 Графический анализ сверху вниз
В первую очередь разбираем тему, то что мы ищемТреугольная минимальная сумма пути, Что это значит? Предположим, у нас есть треугольник: [[2], [3,4], [6,5,7], [4,1,8,3]]
Тогда минимальная сумма пути сверху вниз будет 2-3-5-1, что равно 11.
Поскольку мы используем массив для определения треугольника, поэтому для нашего анализа мы немного изменим треугольник:
Это эквивалентно растяжению всего треугольника. На этот раз, согласно условиям, данным в заголовке: каждый шаг может двигаться только к соседним узлам в следующей строке. Фактически, это эквивалентно тому, что на каждом шаге мы можем двигаться только на одну позицию вниз или на одну позицию вправо. Преобразуйте его в код.Если позиция элемента, где находится 2, равна [0,0], то мы можем двигаться вниз только до позиции [1,0] или [1,1]. Если позиция 5 равна [2,1], она может перемещаться только на позиции [3,1] и [3,2]. Как показано ниже:
После того, как тема выяснена, теперь приступаем к разбору. Проблема, очевидно, является проблемой поиска оптимального решения и может быть построена из оптимальных решений подзадач. Поэтому мы решаем это с помощью динамического программирования. Во-первых, мы определяем состояние:
dp[i][j] : представляет наименьший путь, содержащий элементы в строке i и столбце j.
Легко придумать нисходящий анализ. И каким бы ни был конечный путь, он должен проходить через верхний элемент, то есть [0,0]. Итак, нам нужно инициализировать dp[0][0].
dp[0][0] = значение элемента в позиции [0][0]
Продолжая анализ, если мы запросим dp[i][j], то он должен переместиться из двух элементов над своей головой.
Например, минимальная сумма путей позиции 5 получается либо из 2-3-5, либо из 2-4-5. Затем выберите меньший из двух путей и меньший. Тогда мы получим уравнение перехода состояний:
Однако у нас есть проблема! За исключением самого верхнего элемента,
Крайний левый элемент может появиться только над своей головой. (2-3-6-4)
Самый правый элемент может исходить только из верхнего левого угла. (2-4-7-3)
Затем мы заметили, что все элементы, расположенные в строке 2, являются специальными элементами (поскольку они могут происходить только из элементов [0,0])
Мы можем напрямую обработать его специально и получить:
dp[1][0] = triangle[1][0] + triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]
Наконец, нам просто нужно найти путь и наименьший в последнем ряду элементов, что и является нашим ответом. который:
l: длина массива dp
результат = min(dp[l-1,0], dp[l-1,1], dp[l-1,2]....)
Подводя итог, мы закончили анализ, и мы выполнили в общей сложности 4 шага:
определить состояние
Суммируйте уравнение перехода состояния
Проанализируйте частные случаи, когда уравнение перехода состояния не может быть удовлетворено.
получить окончательное решение
4.3 Анализ кода
После анализа код становится самодостаточным:
func minimumTotal(triangle [][]int) int {
if len(triangle) < 1 {
return 0
}
if len(triangle) == 1 {
return triangle[0][0]
}
dp := make([][]int, len(triangle))
for i, arr := range triangle {
dp[i] = make([]int, len(arr))
}
result := 1<<31 - 1
dp[0][0] = triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]
dp[1][0] = triangle[1][0] + triangle[0][0]
for i := 2; i < len(triangle); i++ {
for j := 0; j < len(triangle[i]); j++ {
if j == 0 {
dp[i][j] = dp[i-1][j] + triangle[i][j]
} else if j == (len(triangle[i]) - 1) {
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
} else {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
}
}
}
for _,k := range dp[len(dp)-1] {
result = min(result, k)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Запустив приведенный выше код, мы обнаружим, что используемая память слишком велика. Есть ли способ сжать память? Путем наблюдения мы обнаружили, что в нашем нисходящем процессе, по сути, нам нужно использовать только данные, которые были накоплены и рассчитаны на предыдущем уровне, и мы не будем снова обращаться к данным предыдущего элемента. ** Нарисуйте следующим образом:
Оптимизированный код выглядит следующим образом:
func minimumTotal(triangle [][]int) int {
l := len(triangle)
if l < 1 {
return 0
}
if l == 1 {
return triangle[0][0]
}
result := 1<<31 - 1
triangle[0][0] = triangle[0][0]
triangle[1][1] = triangle[1][1] + triangle[0][0]
triangle[1][0] = triangle[1][0] + triangle[0][0]
for i := 2; i < l; i++ {
for j := 0; j < len(triangle[i]); j++ {
if j == 0 {
triangle[i][j] = triangle[i-1][j] + triangle[i][j]
} else if j == (len(triangle[i]) - 1) {
triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
} else {
triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
}
}
}
for _,k := range triangle[l-1] {
result = min(result, k)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Пятая серия динамического программирования: минимальная сумма путей
В предыдущем разделе мы успешно завершили решение задачи динамического программирования «минимальной суммы путей треугольников» посредством анализа. В этом разделе мы продолжим рассмотрение вопросов подобного типа, чтобы полностью понять проблему «суммы путей». Без лишних слов, давайте рассмотрим тему:
5.1 Минимальная сумма пути
Вопрос: Дана сетка неотрицательных целых чисел размера m x n. Найдите путь из левого верхнего угла в правый нижний угол, чтобы сумма чисел на пути была наименьшей. Описание: Вы можете двигаться вниз или вправо только на один шаг за раз.
Пример:
входить:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Выход: 7
Объяснение: Потому что сумма путей 1→3→1→1→1 наименьшая.
5.2 Графический анализ
Первым делом разбираем задачу, ищем минимальную сумму пути, что это значит? Предположим, у нас есть прямоугольник m*n: [[1,3,1],[1,5,1],[4,2,1]]
Минимальная сумма пути из левого верхнего угла в правый нижний угол, легко видеть, что это 1-3-1-1-1, а результат этого пути равен 7.
Тема ясна, и мы продолжаем анализировать. Эта задача такая же, как и предыдущая, чтобы найти минимальную сумму путей треугольника.Задача, очевидно, непротиворечива и может быть построена из оптимального решения подзадачи, поэтому мы рассматриваем возможность использования динамического программирования для ее решения. Во-первых, мы определяем состояние:
dp[i][j] : представляет наименьший путь, содержащий элементы в строке i и столбце j.
Аналогично, ведь любой путь в правый нижний угол будет проходить через элемент [0,0]. Итак, нам нужно инициализировать dp[0][0].
dp[0][0] = значение элемента в позиции [0][0]
Продолжаем анализировать, согласно условиям, заданным в заголовке, если мы запрашиваем dp[i][j], то он должен двигаться сверху или слева от себя. Как показано ниже:
5, можно перемещать только из 3 или 1
2, можно переместить только из 5 или 4
4, перейти от 1
3, перейти от 1
Красная позиция должна быть перемещена из синей позиции
Опять же, нам нужно рассмотреть два частных случая:
Верхний ряд, который можно перемещать только слева (1-3-1)
Крайний левый столбец, который можно перемещать только сверху (1-1-4)
Наконец, поскольку наша цель — перейти из левого верхнего угла в правый нижний угол, минимальная сумма путей всей сетки на самом деле является минимальной суммой путей, содержащей нижний правый угловой элемент. который:
Пусть: длина dp равна l
Окончательный результат: dp[l-1][len(dp[l-1])-1]
Подводя итог, мы закончили анализ, и мы выполнили в общей сложности 4 шага:
определить состояние
Суммируйте уравнение перехода состояния
Проанализируйте частные случаи, когда уравнение перехода состояния не может быть удовлетворено.
получить окончательное решение
5.3 Анализ кода
После анализа код становится самодостаточным:
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return 0
}
dp := make([][]int, l)
for i, arr := range grid {
dp[i] = make([]int, len(arr))
}
dp[0][0] = grid[0][0]
for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
if i == 0 && j != 0 {
dp[i][j] = dp[i][j-1] + grid[i][j]
} else if j == 0 && i != 0 {
dp[i][j] = dp[i-1][j] + grid[i][j]
} else if i != 0 && j != 0 {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
}
return dp[l-1][len(dp[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Опять же, запустив код выше, мы видим, что используемая память слишком велика. Есть ли способ сжать память? Путем наблюдения мы обнаружили, что ** в процессе вычисления минимальной суммы путей каждого узла из левого верхнего угла в правый нижний угол нам нужно использовать только данные, которые были накоплены и рассчитаны ранее, ** и будет не обращаться к данным предыдущего элемента снова. Он нарисован следующим образом: (Вы можете видеть, что этот процесс не похож на траление мин. На самом деле, если вы изучите плагины траления мин, вы обнаружите, что в ядре алгоритма траления есть метод анализа, который довольно похоже на этот метод анализа, поэтому я не буду здесь углубляться в него)
Оптимизированный код выглядит следующим образом:
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return 0
}
for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
if i == 0 && j != 0 {
grid[i][j] = grid[i][j-1] + grid[i][j]
} else if j == 0 && i != 0 {
grid[i][j] = grid[i-1][j] + grid[i][j]
} else if i != 0 && j != 0 {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
}
}
}
return grid[l-1][len(grid[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Во всех руководствах этой серии не используются сложные языковые функции, и вам не нужно беспокоиться о том, что вы не выучите go. Идея алгоритма — самая важная, а использование go — сугубо авторское хобби.
Оригинальный текст был впервые опубликован в публичном аккаунте — Хаози рассказывает об алгоритме