Многие думают, что динамическое программирование — это сложно, и даже думают, что собеседование на темы динамического программирования смущает кандидатов, что может привести к неправильному подсознанию: думать, что динамическое программирование не нужно осваивать.
На самом деле динамическое программирование очень нужно освоить:
- Очень осознанное упражнение. Динамическое программирование очень хорошо тренирует мозг.Хотя существуют процедуры, решение каждой проблемы очень разное, поэтому оно очень подходит в качестве упражнения на мышление.
- Очень практично. Динамическое программирование звучит продвинуто, но на самом деле идеи и проблемы, которые оно решает, очень распространены.
Динамическое программирование используется для решения оптимального решения при определенных условиях, таких как:
- Каков наилучший способ автоматического поиска пути?
- Какие предметы в рюкзаке занимают больше всего места?
- Как сделать сдачу с наименьшим количеством монет?
На самом деле, эти вопросы довольно сложны на первый взгляд, ведь это не те вопросы, на которые можно ответить с первого взгляда. Но получить оптимальное решение очень важно, кто выдержит обход алгоритма поиска пути в игре? Кто не хочет больше вещей в рюкзаке? Поэтому мы должны изучить динамическое программирование.
интенсивное чтение
Динамическое программирование — это не волшебство, оно тоже пытается ответить методом перебора, но способом более «умным», так что временная сложность на самом деле не высока.
Разница между динамическим программированием и алгоритмами грубой силы и поиска с возвратом
Приведенное выше предложение также показывает, что все проблемы динамического программирования могут быть решены методом грубой силы! Да, все проблемы с оптимальным решением можно попробовать методом грубой силы (и поиска с возвратом), чтобы найти оптимальное решение.
Алгоритмы грубой силы могут решить почти все. Характерной чертой алгоритма поиска с возвратом является то, что он перебирает разные ветки грубой силой и, наконец, выбирает маршрут с лучшим результатом.
В динамическом программировании также есть концепция ветвей, но вместо того, чтобы пробовать каждую ветвь до конечной точки, при достижении пересечения развилки вы можете напрямую вывести оптимальное решение для следующего шага на основе производительности предыдущих ветвей! Однако и прямой вывод, и предыдущие отраслевые суждения носят условный характер. Решаемая задача динамического программирования должна одновременно удовлетворять следующим трем характеристикам:
- Имеется оптимальная подструктура.
- Существует дублирующая подзадача.
- Никаких последствий.
Существует оптимальная подструктура
То есть оптимальное решение подзадачи может быть получено из глобального оптимального решения.
Что такое подзадачи? Например, в алгоритме поиска пути прохождение первых нескольких шагов является подзадачей, относящейся к полному путешествию.Должно быть гарантировано, что кратчайший путь к полному путешествию может быть получен путем выполнения первых нескольких шагов, прежде чем можно будет приступить к динамическому программированию. использовал.
Не стоит недооценивать этот первый пункт, динамическое программирование здесь затруднено, как установить взаимосвязь между оптимальной подструктурой и глобальным оптимальным решением?
- Для задачи подъема по лестнице, поскольку каждый шаг поднимается из предыдущих шагов, должен быть вывод линейной зависимости.
- Что, если это станет двухмерным поиском пути? Затем она обновляется до двумерной задачи, есть две переменные
i,jотносящийся к предыдущему шагу. - Если это проблема рюкзака, есть также количество предметов
i, Вес предметаjи качество товараkКак насчет трех переменных? Затем она обновляется до трехмерной задачи, и необходимо найти взаимосвязь между тремя.
И так далее, сложность может возрасти до N измерений, чем выше размерность, тем выше сложность мышления, и тем больше пространственной сложности нужно оптимизировать.
Есть повторяющиеся подзадачи
То есть одна и та же подзадача имеет повторяющиеся расчеты в разных сценариях.
Например, в алгоритме поиска пути при расчете тех же двух маршрутов есть участок маршрута, который является общим и единственным способом прохождения расчета, поэтому его достаточно рассчитать только один раз. следующий маршрут, если вы встретите этот подмаршрут, сразу просто возьмите кэш первого расчета. Типичным примером является последовательность Фибоначчи, дляf(3)а такжеf(4), быть рассчитаннымf(1)а такжеf(2),потому чтоf(3) = f(2) + f(1),а такжеf(4) = f(3) + f(2) = f(2) + f(1) + f(2).
Это ключевое различие между динамическим программированием и решениями грубой силы.Причина, по которой динамическое программирование является высокопроизводительным, заключается в том, чтоНет повторяющихся подсчетов для повторяющихся подзадач, алгоритм обычно решается путем кэширования результатов вычислений или восходящей итерации, но суть в том, что в этом сценарии должны быть повторяющиеся подзадачи.
Когда вы думаете, что решение методом перебора может быть глупым и есть много повторяющихся вычислений, вам нужно подумать о том, где есть повторяющиеся подзадачи и можно ли их решить с помощью динамического программирования.
нет последействия
То есть предыдущий выбор не повлияет на последующие правила игры.
В алгоритме поиска пути следующий маршрут не будет затронут, потому что маршрут B выбран впереди. Поскольку последовательность Фибоначчи детерминистически связана с N-м элементом и предыдущим элементом, выбора нет, поэтому нет проблемы последействия.
Какие сценарии имеют последствия? Например, можете ли вы найти оптимальное решение в своей жизни с помощью динамического программирования? На самом деле это невозможно, потому что ваш выбор сегодня может повлиять на траекторию вашей жизни в будущем.Например, если вы выберете карьеру в области вычислений, это напрямую повлияет на сферу работы, людей, с которыми вы вступаете в контакт ,и жизненный путь в будущем.Поэтому нельзя Сравнивать с вами,выбравшим гражданское строительство,потому что жизненный путь изменился.
Некоторые студенты могут подумать, что это ограничение слишком велико? На самом деле, есть еще много проблем без последствий, например, какой предмет положить в рюкзак, какой маршрут вы сейчас выбираете, и какое изменение вы используете, все это не повлияет на размер всего рюкзака, местность всей карты, и самая важная для вас сумма платежа.
Процедура решения — уравнение перехода состояния
Суть решения задачи динамического программирования заключается в написании уравнения перехода состояния.
Уравнение перехода состояния обычно записывается какdp(i) = 一系列 dp(j) 的计算,вj < i.
вiа такжеdp(i)Смысл очень важен, вообщеdp(i)непосредственно представлять ответ на вопрос,iЕсть мастерство. Подобно последовательности Фибоначчи,dp(i)Указанный ответ является окончательным результатом,iПредставляет нижний индекс, потому что последовательность Фибоначчи напрямую говорит вам уравнение перехода состоянияf(x) = f(x-1) + f(x-2), то вывод вообще не нужен.
Для сложных задач трудно определитьiЗначение и то, как следующее состояние получается из предыдущего состояния.Если вы сделали больше тем, у вас будет опыт, если нет, то будет сложно объяснить, как это объяснить, поэтому давайте просто рассмотрим пример позже.
Начнем с простейшего примера динамического программирования — подъема по лестнице, чтобы проиллюстрировать проблему.
проблема с подъемом по лестнице
Подъем по лестнице - простая задача, тема следующая:
Предположим, вы поднимаетесь по лестнице. нужно
nшаги, чтобы достичь вершины. Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания? (даноnявляется положительным целым числом)
первыйdp(i)является ответом на вопрос (программа решения,dp(i)В большинстве случаев ответ есть ответ, поэтому идея решения задачи будет максимально упрощенной), то есть лезть на первыйiколичество методов для шагов, затемiЕстественно, вам придется подняться на первые несколько ступенек.
Сначала мы видим, есть лиоптимальное основание? Потому что подняться можно только вверх, первыйiЕсть несколько способов подняться по ступенькам, в зависимости от того, сколько способов подняться впереди.Вы можете подняться только на 1 или 2 ступеньки за раз, поэтому перваяiШаги возможны только изi-1илиi-2поднялся по лестнице, так первыйiСпособ подняться по лестницеi-1а такжеi-2Сумма всех подъемов. Следовательно, оптимальная подструктура, очевидно, существует, и даже готово появиться уравнение перехода состояния.
посмотрите, существует ли онЕсть повторяющиеся подзадачи, на самом деле восхождение по лестнице похоже на последовательность Фибоначчи, и уравнение перехода в конечное состояние такое же, так что, очевидно, есть повторяющаяся подзадача. Конечно, это также легко анализировать интуитивно.Метод подъема по лестнице из 10 шагов включает методы подъема по 8-й и 9-й ступеням, а метод подъема по лестнице из 9-ти шагов включает в себя 8-й шаг, поэтому есть повторяющиеся подзадачи.
Наконец, посмотрите, еслинет последействия? Поскольку предыдущий выбор подъема на 1 или 2 ступени за раз не влияет на общее количество ступеней, а также на количество ступеней, которые вы сможете пройти в следующий раз, никаких последствий не возникает. Если вы поднялись на 2 ступеньки, потому что слишком устали, в следующий раз вы сможете подняться только на 1 ступеньку, что является последствием. Или пока вы поднялись 3 раза и всего 2 ступени, вы откажетесь от подъема по лестнице, потому что слишком устали, и сразу пойдете вниз отдыхать, тогда проблема закончится раньше, что тоже является последствием.
Итак, уравнение перехода состояния для подъема по лестнице:
dp(i) = dp(i-1) + dp(i-2)dp(1) = 1dp(2) = 2
Обратите внимание, что требуется специальное перечисление, потому что общие уравнения перехода состояния не могут быть применены к шагам 1 и 2. Эта идея перечисления фактически находится в кодерекурсивное условие завершения, то есть как функцияdp(i)не может рекурсировать бесконечно, когдаiКогда значение равно 1 или 2, результат перечисления возвращается напрямую (для этой проблемы). Поэтому при написании рекурсии обязательно сначала напишите условие завершения рекурсии.
Тогда считаем, что для первой ступени есть только один способ лазания, что не вызывает возражений. Для второго шага вы можете сразу сделать два шага, или вы можете сделать два шага, так что есть два метода лазания, и это легко понять.Здесь проблема решена.
Что касается кодовой части, просто напишите этот вопрос, если нет особых причин для следующих вопросов, код не будет написан:
function dp(i: number) {
switch (i) {
case 1:
return 1;
case 2:
return 2;
default:
return dp(i - 1) + dp(i - 2);
}
}
return dp(n);
Конечно, запись таким образом многократно вычисляет подструктуру, поэтому мы не хотим каждый раз выполнять ее тупо.dp(i - 1)(Поскольку это вычисляет много повторяющихся подзадач), нам нужно использовать кеш, чтобы добраться до сути:
const cache: number[] = [];
function dp(i: number) {
switch (i) {
case 1:
cache[i] = 1;
break;
case 2:
cache[i] = 2;
break;
default:
cache[i] = cache[i - 1] + cache[i - 2];
}
return cache[i];
}
// 既然用了缓存，最好子底向上递归，这样前面的缓存才能优先算出来
for (let i = 1; i <= n; i++) {
dp(i);
}
return cache[n];
Конечно, это просто одномерный линейный кеш, более продвинутые режимы кешакеш прокрутки. Мы заметили, что накладные расходы на кэш-память для этого вопросаO(n), но каждый раз при использовании кеша используются только два последних значения, поэтому вычислениеdp(4)час,cache[1]Его можно выкинуть, а можно использовать кеш для прокрутки, пустьcache[3]Занятьcache[1]пространство, то общая сложность пространства может быть уменьшена доO(1), конкретный метод:
const cache: [number, number] = [];
function dp(i: number) {
switch (i) {
case 1:
cache[i % 2] = 1;
break;
case 2:
cache[i % 2] = 2;
break;
default:
cache[i % 2] = cache[(i - 1) % 2] + cache[(i - 2) % 2];
}
return cache[i % 2];
}
for (let i = 1; i <= n; i++) {
dp(i);
}
return cache[n % 2];
Взяв остаток, ловко пусть тайник попеременно занимает навсегдаcache[0]а такжеcache[1], чтобы максимально использовать пространство. Конечно, эту проблему можно оптимизировать, поскольку первые два уравнения перехода состояний используются последовательно.Если вы сталкиваетесь с уравнениями перехода состояний, которые используют все предыдущие кэши, вы не можете использовать решение с скользящим кэшем. Однако есть и более продвинутые многомерные кэши, о которых речь пойдет позже.
Далее, давайте рассмотрим сложную задачу, максимальную сумму подзаказов.
максимальная сумма подзаказа
Максимальная сумма подзаказов — простая задача, тема следующая:
задан массив целых чисел
nums, найти непрерывный подмассив с наибольшей суммой (подмассив содержит хотя бы один элемент) и вернуть его наибольшую сумму.
Сначала следуйте рутине подъема по лестнице,dp(i)Это означает максимальную сумму, Поскольку в массиве целых чисел могут быть отрицательные числа, чем больше чисел добавлено, тем больше сумма не обязательно больше.
см. далееi, для задач с массивами большинствоiможет представлятьiстрока с завершающим битом, затемdp(i)значитiМаксимальная сумма строк с битовым завершением.
Может быть, вы думаетеiВ конце концов, это может быть только[0-i]диапазон значений, то[j-i]Разве диапазоны строк не игнорируются? вообще-то нет,[j-i]Если это самая большая сумма, она также будет включена вdp(i), потому что наше уравнение перехода состояния может не связыватьdp(i-1).
Теперь начнем решать задачу: во-первых, задача состоит в непрерывном подмассиве наибольшей суммы.Как правило, непрерывные подмассивы относительно просты, потому что дляdp(i), либо подключенный к передней части, либо отключенный от передней части, поэтому уравнение перехода состояния:
-
dp(i) = dp(i-1) + nums[i]еслиdp(i-1) > 0. -
dp(i) = nums[i]еслиdp(i-1) <= 0.
Как понять это? первыйiСостояние может быть непосредственно определеноi-1состояние является производным, так какdp(i)означает первыйiмаксимальная сумма в конце строки, тогдаdp(i-1)первыйi-1максимальная сумма в конце строки, и в это времяdp(i-1)был рассчитан, тоdp(i)Понятно, как вывести:
Поскольку строки являются смежными, поэтомуdp(i)либоdp(i-1) + nums[i], или напрямуюnums[i], поэтому какой из них выбрать, зависит от предыдущегоdp(i-1)это положительное число,потому что сiдолжен содержать в концеnums[i],такnums[i]Будь то положительный или отрицательный, вы должны принести его.Так легко узнать,dp(i-1)Если это положительное число, то оно связано, в противном случае оно не связано.
Что ж, после такого подробного объяснения, я считаю, что вы полностью поняли процедуру решения задач динамического программирования, я не буду так многословен в объяснении следующих вопросов!
Если эта задача немного сложнее, что, если она не является непрерывной? Рассмотрим задачу о самой длинной возрастающей подпоследовательности.
самая длинная возрастающая подпоследовательность
Самая длинная возрастающая подпоследовательность — это задача среднего размера со следующими вопросами:
дает вам массив целых чисел
nums, найти в ней длину самой длинной строго возрастающей подпоследовательности.Подпоследовательность — это последовательность, полученная из массива, которая удаляет (или не удаляет) элементы из массива без изменения порядка оставшихся элементов. Например,
[3,6,2,7]это массив[0,3,1,6,2,2,7]подпоследовательность.
На самом деле, преждеИнтенсивное чтение «DOM diff самая длинная восходящая подпоследовательность»Эта проблема была подробно проанализирована, включая лучшее жадное решение, но на этот раз мы сосредоточимся на методе динамического программирования.
Отличие этого вопроса от предыдущего в том, что он, во-первых, инкрементный, а во-вторых, прерывистый.
В соответствии с формулой,dp(i)значитiКонец самой длинной строки увеличенной длины последовательности, затем фокус,dp(i)Как вывести его из предыдущего вывода?
Поскольку он прерывистый, вы не можете просто смотреть наdp(i-1), потому чтоnums[i]пункт сdp(j)(в0 <= j < i) может достигать максимальной длины после объединения, поэтому необходимо пройти всеj, попробуйте комбинацию с наибольшей длиной среди них.
Итак, уравнение перехода состояния:
dp[i] = max(dp[j]) + 1,в0<=j<iа такжеnum[j]<num[i].
Появление этого вопроса знаменует появление более сложного уравнения перехода состояний, т. е. первогоiтермин не простоi-1производное, а от всех предыдущихdp(j)вывод, где0<=j<i.
Кроме того, существуют производные варианты, основанные наdp(dp(i))Вывод, то есть функция внутри функции, задача такого рода относительно сложнее, потому что она углубляет слой мыслительных мозговых цепей. Давайте рассмотрим такую задачу: самая длинная значащая скобка.
самая длинная значащая скобка
Самая длинная допустимая скобка - сложная задача со следующими вопросами:
дает вам тот, который содержит только
'('а также')', найдите длину самой длинной допустимой (правильной и непрерывной) подстроки в скобках.
Причина, по которой этот вопрос сложен, заключается в вложенном мышлении в уравнении перехода состояния.
Сначала мы определяем по рутинеdp(i)как ответ, то есть первыйiСамая длинная допустимая длина скобки в строке, заканчивающейся нижним индексом. Ты это видел? В общих вопросах строки,iВсе они определены в конце нижнего индекса строки, и некоторые из них определены как начало или другое определенное поведение. Конечно, это не относится к неструнным задачам, которые будут обсуждаться позже.
Продолжаем вопрос, еслиs[i]да(, то невозможно сформировать допустимые скобки, потому что крайняя правая не должна быть закрыта, поэтому рассмотримs[i]для)место действия.
еслиs[i-1]для(, то составляет...(), последние два самодостаточны и юридически закрыты, так что просто посмотрите на предыдущие, т.е.dp(i-2), поэтому уравнение перехода состояния для этого сценария:
dp(i) = dp(i-2) + 2
еслиs[i-1]да)Шерстяная ткань? составленный...))государство, то толькоi-1является юридически закрытым, и этому юридически закрытому сегменту должен предшествовать(с первымiТермин закрыт, чтобы составить самую длинную эффективную длину скобки на данный момент, поэтому уравнение перехода состояния для этого сценария:
dp(i) = dp(i-1) + dp(i - dp(i-1) - 2) + 2, вы можете понять с помощью следующей схемы:
можно увидеть,dp(i-1)Это длина второй горизонтальной линии, и затем, если красные скобки совпадают, длина снова +2, и, наконец, не забудьте привести крайнюю левую, если есть совпадение, этоdp(i - dp(i-1) - 2), поэтому сложение их вместе — это максимальная длина круглых скобок для этого сценария.
На данный момент глубина проблемы одномерного динамического программирования в основном изучена. Прежде чем перейти к проблеме многомерного динамического программирования, есть тип задачи одномерного динамического программирования. Ее нетрудно выразить, и есть нет такого сложного вложенного DP, как эта проблема, но мышление очень сложное,Вы не должны смотреть на весь процесс, потому что сложность слишком высока, вам нужно полностью осознать смысл той части, которая была вычислена с помощью dp (i-x), и вести высоко абстрактное мышление.
Раскраска забора
Раскрашивание забора — сложная задача со следующими темами:
имеют
kцвета краски и содержащиеnЗабор из столбов, каждый из которых можно покрасить в один из цветов.Вам нужно покрасить все столбы забора и убедиться, что столбы забора примыкают к ним.До двух последовательныхТакого же цвета. Затем возвращает количество всех допустимых цветовых схем.
этот вопросkа такжеnОба являются огромными, обычными решениями для грубой силы, и даже обычные DP будут истекать по тайм-ауту. выберитеiЗдесь также важен смыслiВ конце концов, это несколько цветов или несколько заборов? Забор выбрать проще, потому что забор — это основная часть раскраски. такdp(i)перед окрашиваниемiВсе цветовые решения для каждого забора.
Сначала посмотрите на условие рекурсивного завершения. Так как не более двух последовательных цветов одинаковы, тоdp(0)а такжеdp(1)соответственноkа такжеk*k, потому что каждый забор окрашен случайным образом и свободно комбинируется. Такdp(2)Есть три забора.Незаконная ситуация заключается в том, что все три забора одного цвета, поэтому используйте все возможные, чтобы вычесть незаконный, а незаконная сцена толькоk, так что результатk*k*k - k.
Тогда рассмотрим общий случай, дляdp(i)Сколько существует цветовых схем? Ситуаций слишком много, чтобы прямо обдумывать, делим ситуацию на две, рассматриваемiа такжеi-1Рассматриваются два случая одного и разных цветов.
еслиiа такжеi-1того же цвета, то для легитимности,i-1точно не сi-2Цвет тот же, иначе есть три одного цвета, в этом случае неважноi-2Какого цвета это,i-1а такжеiВы можете взять только на один цвет меньше, и чем меньшеi-2цвет, так[i-1,i]Этот диапазон имеетk-1Средняя цветовая гамма с передней частьюdp(i-2)Существуют различные цветовые схемы, и умножение является конечным номером схемы:dp(i-2) * (k-1).
На самом деле за этим стоит динамическое мышление, т.k-1все разные цветовые комбинации, только не важно спередиdp(i-2)Какое сочетание должны иметь последние два забораk-1Таким образом, хотя цветовые значения цветовых комбинаций различны, количество цветовых комбинаций остается неизменным, поэтому его можно рассчитать единообразно. Понимание этого имеет решающее значение.
еслиiа такжеi-1разные цвета, тоiтолько предметk-1Этот метод также динамичен, потому что его никогда нельзя сравнивать сi-1Такого же цвета. Наконец умножитьdp(i-1)Цветовая схема , это общее количество схем:dp(i-1) * (k-1).
Таким образом, окончательное общее количество вариантов равно сумме двух, а именноdp(i) = dp(i-2) * (k-1) + dp(i-1) * (k-1).
Отличие в этом вопросе в том, что изменений слишком много, и цвет любого забора повлияет на цвет забора позади.На первый взгляд кажется, что это проблема с последствиями, которую нельзя решить с помощью динамического программирования.. Но на самом деле хоть и есть последствия, но если провести разумный демонтаж, то полная возможность забора сзадиk-1постоянно,Таким образом, учитывая общее количество возможностей, никакого последействия нет., поэтому можно решить эту проблему, абстрактно размышляя об общем количестве решений.
Далее следует введение в многомерное динамическое программирование, начиная с двух измерений. Двумерное динамическое программирование заключается в использовании двух переменных для представления DP, а именноdp(i,j), как правило, происходит в сценариях с двумерными массивами.Конечно, существуют также некоторые отношения между двумя массивами, которые также относятся к двумерному динамическому программированию.Чтобы продолжить обсуждение проблемы строк, я выбрал двумерное динамическое программирование Пример проблемы со строками. Отредактируйте расстояние до этого вопроса, чтобы объяснить.
изменить расстояние
Редактировать расстояние — сложная задача со следующими темами:
дать вам два слова
word1а такжеword2, посчитайте пожалуйстаword1Перевести вword2Минимальное количество используемых операндов.Над словом можно выполнить следующие три операции:
- вставить символ
- удалить персонажа
- заменить символ
Пока это проблема строки, в основномiоба указывают на то, чтоiстрока, оканчивающаяся термином, но этот вопрос состоит из двух строк слов,Чтобы рассмотреть произвольные сценарии сопоставления, он должен быть представлен двумя переменными, а именноi jСоответственноword1а такжеword2Когда заканчиваются индексы, минимальное количество операций.
тогда дляdp(i,j)рассмотреть возможностьword1[i]а такжеword2[j]То же самое, наконец, через двойную рекурсию, первую рекурсиюi, рекурсивно внутри рекурсииj, ответ вышел.
Предполагая, что последний символ тот же, т.е.word1[i] === word2[j]час,Так как последний символ тот же без изменения, количество операций эквивалентно учету предыдущего символа,Прямо сейчасdp(i,j) = dp(i-1,j-1)
Предполагая, что последний символ отличается, тогдапоследний шагДоступны три режима:
- Предположим, что это замена, т.е.
dp(i,j) = dp(i-1,j-1) + 1, потому что для замены последнего символа требуется всего один шаг, и он не имеет ничего общего с предыдущими символами, поэтому непосредственно добавляется минимальное количество операций впереди. - Предположим, что это вставка, т.е.
word1вставка символа становитсяword2, то просто перейдите к этому шагу и добавьте к операции вставки +1. После перехода к этому шагу достаточно вставить один, поэтомуword1Сравниватьword2Одним словом меньше, все остальное то же самое, для перехода на этот шаг необходимо выполнитьdp(i,j-1)трансформация, такdp(i,j) = dp(i,j-1) + 1. . - Предполагается удалить, т.е.
word1удалить символ становитсяword2, так же провестиdp(i-1,j)После изменения удален еще один шаг, поэтомуdp(i,j) = dp(i-1,j) + 1.
Поскольку заголовок требует минимального количества операций, то можно взять минимальное из этих трех условий, т. е.dp(i,j) = min(dp(i-1,j-1), dp(i,j-1), dp(i-1,j)) + 1.
Таким образом, после рассмотрения того, является ли последний символ одинаковым, комбинированное уравнение перехода состояния является окончательным ответом.
Затем рассмотрим условие завершения, а именноiилиjравен -1, потому что уравнение перехода состоянияiа такжеjПостоянно уменьшаясь, оно обязательно уменьшится до 0 или -1, потому что 0 — это строка с еще одним символом, что относительно удобно при рассмотрении -1, когда строка пуста, поэтому мы рассматриваем -1 как граничное условие.
когдаiКогда -1, то естьword1пуст, его следует преобразовать вword2Очевидно, только вставитьjраз — минимальное количество операций, поэтому на этот разdp(i,j) = j; Аналогично, когдаjКогда -1, то естьword2пусто, удалить в данный моментiраз, поэтому число операций равноi,такdp(i,j) = i.
нестроковый вопрос
Говоря об этом, я полагаю, что вы уже знакомы с проблемой строковых глаголов, давайте посмотрим на глаголы в нестроковых сценариях. Классических правил движения для неструнных сценариев три: первое — минимальное расстояние прямоугольного пути, или максимальная прибыль, второе — задача о рюкзаке и ее варианты, третье — задача об ограблении.
Эти задачи решаются одинаково, за исключениемdp(i)Определение немного отличается, например, для задачи прямоугольника,dp(i,j)значит идтиi,jминимальный путь в решетке, для задачи о рюкзакеdp(i,j)Указывает, что первыйiвещи остались в рюкзакеjМаксимальная цена за космос; за проблему грабежа,dp(i)означает грабежiМаксимальная выгода для одного номера.
Из-за проблемы пространства я не буду вводить ее здесь подробно, а только кратко объясню прямоугольную проблему и проблему грабежа.
Для задачи прямоугольника уравнение перехода состояния фокусируется на том, как передается предыдущее состояние.Как правило, прямоугольник можно перемещать только вправо или вниз, и на пути могут быть некоторые препятствия.Значение требуемого маршрута как текущегоdp(i)Уравнение переноса .
Для проблемы грабежа, поскольку соседние дома нельзя грабить одновременно,dp(i)или за грабежi-1а не грабитьiкомната или ограблениеi-2Ю ДиiМожно взять максимальное значение этих двух конечных состояний, т. е.dp(i) = max(dp(i-1), dp(i-2) + coins[i]).
Суммировать
Ядро динамического программирования разделено на три этапа.Во-первых, состояние четко определено, а именноdp(i)Что это такое? Затем определите уравнение перехода состояния. Этот шаг требует некоторых навыков мышления. Наконец, подумайте о проверке правильности, то есть попытайтесь доказать, что уравнение перехода состояния, которое вы написали, верно. В этом процессе переход состояния должен быть сделано тщательно Все ситуации покрыты.
Самая классическая задача динамического программирования — задача о рюкзаке, из-за недостатка места она может быть представлена в отдельной статье в следующий раз.
Адрес обсуждения:Алгоритмы интенсивного чтения — динамическое программирование · Выпуск №327 · dt-fe/weekly
Если вы хотите принять участие в обсуждении, пожалуйста,кликните сюда, с новыми темами каждую неделю, выходящими по выходным или понедельникам. Интерфейс интенсивного чтения — поможет вам отфильтровать надежный контент.
Сфокусируйся наАккаунт WeChat для интенсивного чтения в интерфейсе
Заявление об авторских правах: Бесплатная перепечатка - некоммерческая - не производная - сохранить авторство (Лицензия Creative Commons 3.0)