предисловие
В предыдущем блоге было кратко изложено динамическое программирование, но для новичка, такого как я, есть еще много мест, которые я не могу понять, поэтому я нашел отличное объяснение в Интернете, и это действительно здорово. Переведено.
Оригинальная ссылка нижеиспользованная литература.
1. Подробное объяснение процедур динамического программирования
Ниже приводится подробное объяснение динамического программирования с помощью последовательности Фибоначчи и этой проблемы изменения.Если вы хотите увидеть только ответ на этот вопрос, прокрутите страницу до конца..
Алгоритм динамического программирования кажется очень непредсказуемым алгоритмом. Вы увидите соответствующий контент в разделе продвинутых навыков некоторых интервью или книг по алгоритмам. Что такое уравнения перехода состояний, перекрывающиеся подзадачи, оптимальные подструктуры и другая высокоуровневая лексика. ты прочь.
Кроме того, когда вы смотрите на код, использующий динамическое программирование для решения проблемы, и думаете, что это настолько гениальное решение проблемы, его трудно понять, и вы можете быть удивлены, как люди придумывают это решение.
На самом деле, динамическое программирование - это обычная "техника проектирования алгоритмов", и в ней нет ничего непостижимого. Что касается различных высокоуровневых терминов, то они используются, чтобы пугать других. Пока вы испытываете несколько, смысл этих терминов на самом деле Понятно, что проще некуда.
Что касается того, почему окончательное решение выглядит таким тонким, это потому, что динамическое программирование следует за фиксированным процессом:Рекурсивное решение грубой силы -> рекурсивное решение с мемоизацией -> решение нерекурсивного динамического программирования. Этот процесс представляет собой пошаговый процесс решения проблем, и если вы не имеете предыстории и смотрите прямо на окончательное решение нерекурсивного динамического программирования, конечно, вы почувствуете, что оно слишком крутое и из ряда вон выходящее. достигать.
Конечно, чем больше вы видите и чем больше думаете об этом, вы можете написать решение для нерекурсивного динамического программирования за один шаг. Любой навык нужно практиковать. Сначала мы следуем этому процессу, а дизайн алгоритма - это просто эти процедуры. Кроме этого, на самом деле нет ничего продвинутого.
Ниже, сначала на двух относительно простых примерах: Фибоначчи и проблема внесения изменений, раскрывается тайна динамического программирования и описываются три вышеупомянутых процесса. В будущем я напишу несколько статей о том, как использовать методы динамического программирования для решения более сложных классических задач.
Прежде всего, первый пример, который вот-вот разобьют, — последовательность Фибоначчи. Пожалуйста, не пренебрегайте простотой этого примера, потому что простой пример может позволить вам полностью сконцентрироваться на общих идеях и методах, лежащих в основе алгоритма, и не быть сбитым с толку этими неясными деталями. Последующие, есть трудные примеры.
Шаг 1. Рекурсивный алгоритм грубой силы
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
Излишне говорить, что школьные учителя используют это как пример, когда говорят о рекурсии. Мы также знаем, что хотя написание кода таким образом является кратким и простым для понимания, это очень неэффективно. Предполагая n = 20, нарисуйте дерево рекурсии.
PS:Всякий раз, когда вы сталкиваетесь с проблемой, требующей рекурсии, лучше всего нарисовать дерево рекурсии, которое поможет вам проанализировать сложность алгоритма и найти причину неэффективности алгоритма.
Как понять это дерево рекурсии? То есть, чтобы вычислить исходную задачу f(20), я должен сначала вычислить подзадачи f(19) и f(18), а затем, чтобы вычислить f(19), я должен вычислить подзадачи. сначала задачи f(18) и f(18), f(17) и так далее. Наконец, когда встречается f(1) или f(2), результат известен, и результат может быть возвращен напрямую, и рекурсивное дерево больше не растет вниз.
Как рассчитать временную сложность рекурсивного алгоритма? Умножьте количество подзадач на время, необходимое для решения подзадачи.
Количество подзадач, то есть общее количество узлов в дереве рекурсии. Очевидно, что общее количество узлов бинарного дерева экспоненциально, поэтому количество подзадач равно O(2^n).
Время решения подзадачи, в этом алгоритме нет цикла, только f(n - 1) + f(n - 2) является операцией сложения, а время равно O(1).
Таким образом, временная сложность этого алгоритмаO(2^n), экспоненциальный уровень, взрыв.
Глядя на рекурсивное дерево, очевидно, что причина неэффективности алгоритма найдена: много повторяющихся вычислений, например, f(18) вычисляется дважды, и видно, что рекурсивное дерево с корнем в f (18) огромен. , потребуется много времени, чтобы вычислить его снова. Более того, многократно вычисляется более одного узла f(18), поэтому этот алгоритм крайне неэффективен.
Это первое свойство задач динамического программирования: перекрывающиеся подзадачи. Ниже мы находим способ решить эту проблему.
Шаг 2. Рекурсивное решение с памяткой
Как только проблема выяснена, фактически половина проблемы решена. Так как причина длительности - повторный расчет, то можно создать "меморандум", и не торопиться возвращаться после расчета ответа на подвопрос, сначала записать его в "меморандум", а потом возвращать ; каждый раз, когда встречается подвопрос, перейдите в «Памятку» и проверьте его. Если вы обнаружите, что эта проблема уже решалась раньше, просто используйте ответ напрямую и не тратьте больше времени на вычисления.
Обычно в качестве этой «памятки» используется массив, конечно, вы также можете использовать хеш-таблицу (словарь), идея та же.
int fib(int N) {
if (N < 1) return 0;
// 备忘录全初始化为 0
vector<int> memo(N + 1, 0);
return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
if (n == 1 || n == 2) return 1;
if (memo[n] != 0) return memo[n];
// 未被计算过
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
Теперь нарисуйте дерево рекурсии, и вы точно знаете, что делает «памятка».
По сути, рекурсивный алгоритм с «меморандумом» преобразует рекурсивное дерево с огромным количеством избыточности в рекурсивный граф без избыточности посредством «обрезки», что значительно уменьшает подзадачи (то есть рекурсивное количество узлов в графе ).
Какова временная сложность рекурсивного алгоритма? Умножьте количество подзадач на время, необходимое для решения подзадачи.
Количество подзадач, то есть общее количество узлов в графе.Поскольку в этом алгоритме нет избыточных вычислений, то подзадачами являются f(1), f(2), f(3) ... f(20 ), число и масштаб ввода n = 20 пропорциональны, поэтому количество подзадач равно O (n).
Время решения подзадачи такое же, как и выше, без циклов, время O(1).
Следовательно, временная сложность этого алгоритма равна O(n). По сравнению с насильственными алгоритмами это атака с уменьшением размерности.
Пока что рекурсивное решение с мемоизацией столь же эффективно, как и динамическое программирование. По сути, это решение похоже на идею динамического программирования, за исключением того, что этот метод называется «сверху вниз», а динамическое программирование — «снизу вверх».
Что такое «сверху вниз»? Обратите внимание, что дерево рекурсии (или граф), которое мы только что нарисовали, простирается сверху вниз, начиная с исходной задачи большего масштаба, такой как f(20), и постепенно разлагает шкалу вниз до тех пор, пока f(1) и f(2) не достигнут дна. выход, а затем возвращаться к ответу слой за слоем, это называется «сверху вниз».
Что такое «снизу вверх»? И наоборот, мы начинаем непосредственно с самого нижнего, самого простого и наименьшего размера задачи f (1) и f (2) и продвигаемся вверх, пока не достигнем желаемого ответа f (20), что является идеей динамического программирования. , Вот почему динамическое программирование обычно избавляется от рекурсии, но завершает вычисление итерацией цикла.
Шаг 3: Динамическое программирование
Вдохновившись «меморандумом» на предыдущем шаге, мы можем разделить этот «меморандум» на таблицу, которая называется таблицей DP. Разве не было бы прекрасно завершить вычисление «снизу вверх» на этой таблице!
int fib(int N) {
vector<int> dp(N + 1, 0);
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
Это легко понять, нарисовав картинку, и вы обнаружите, что эта таблица DP очень похожа на результат предыдущей «обрезки», но все наоборот. На самом деле «memo» в рекурсивном решении с memo — это таблица DP после окончательного завершения, поэтому два решения на самом деле похожи, и в большинстве случаев эффективность в основном одинакова.
Вот, выводи«Динамическое уравнение переноса»Термин, по сути, представляет собой математическую форму, описывающую структуру задачи:
Почему оно называется «уравнение перехода состояний»? Чтобы звук был высоким. Вы хотите, чтобы f(n) было состоянием n, это состояние n переносится из сложения состояний n - 1 и состояний n - 2, это называется передачей состояний, вот и все.
Вы обнаружите, что все операции в приведенных выше решениях, такие как return f (n - 1) + f (n - 2), dp [i] = dp [i - 1] + dp [i - 2] и Инициализация операции над меморандумом или таблицей DP - все это разные выражения вокруг этого уравнения. Можно видеть, что важность перечисления «уравнения перехода состояний» является ядром решения проблемы. Легко обнаружить, что на самом деле уравнение перехода состояния непосредственно представляет собой решение грубой силы.
Не смотрите свысока на насильственное решение.Самая трудная часть задачи динамического программирования — написать уравнение перехода состояния, то есть насильственное решение.. Метод оптимизации — это не что иное, как использование меморандума или таблицы DP, в этом нет никакой тайны.
В конце этого примера поговорим о подробной оптимизации. Внимательные читатели обнаружат, что в соответствии с уравнением перехода состояний последовательности Фибоначчи текущее состояние связано только с двумя предыдущими состояниями.На самом деле, такая длинная таблица DP не нужна для хранения всех состояний, просто найдите способ сохранить предыдущее состояние.Всего два состояния. Следовательно, его можно дополнительно оптимизировать, чтобы уменьшить пространственную сложность до O (1):
int fib(int n) {
if (n < 2) return n;
int prev = 0, curr = 1;
for (int i = 0; i < n - 1; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
Некоторые люди могут спросить, почему не рассматривается еще одна важная особенность динамического программирования — «оптимальная подструктура»? будет рассмотрено ниже. Пример последовательности Фибоначчи не является строго динамическим программированием, вышеприведенное предназначено для демонстрации спирали построения алгоритма. Когда задача требует поиска оптимального решения или вы видите в коде такие функции, как циклы и max, min и т. д., по всей вероятности, нужно динамическое программирование.
проблема зарабатывания денег
Теперь посмотрите на второй пример,проблема зарабатывания денег, с приведенным выше подробным предзнаменованием, эта проблема будет решена быстро.
тема: Дайте вам k монет достоинством, номиналы c1, c2 ... ck, а затем дайте общую сумму n, спросите вас, сколько монет вам нужно хотя бы, чтобы восполнить эту сумму, если невозможно восполнить, ответ -1 .
Например, если k = 3, номиналы 1, 2 и 5, а общая сумма n = 11, то требуется минимум 3 монеты, то есть 11 = 5 + 5 + 1. Следуйте описанному ниже процессу.
Решение насилияПервый - самый сложный шаг, выписывание уравнения перехода состояния, которое проще написать:
Фактически это уравнение использует свойство «оптимальной подзадачи»: решение исходной задачи состоит из оптимального решения подзадачи. То есть f(11) переносится из оптимального решения f(10), f(9), f(6).
Помните, чтобы соответствовать «оптимальной подструктуре»,Подзадачи должны быть независимы друг от друга. Что такое взаимная независимость? Вы определенно не хотите видеть математическое доказательство, я объясню его на интуитивном примере.
Например, ваш первоначальный вопрос состоит в том, чтобы получить наивысший общий балл, затем ваш подвопрос состоит в том, чтобы получить наивысший балл по китайскому языку и наивысший балл по математике... Чтобы получить наивысший балл по каждому предмету, вам нужно взять каждый предмет получает наивысший балл. Соответствующие вопросы курсов с несколькими вариантами ответов получают наивысший балл, а вопросы с заполнением пробелов получают наивысший балл... Конечно, в конце концов, вы получаете полные баллы за каждый курс, что является наивысшим общим баллом.
Получен правильный результат: наивысший суммарный балл является общим баллом. Поскольку этот процесс соответствует оптимальной подструктуре, подзадачи «высшего в каждом предмете» независимы друг от друга и не мешают друг другу.
Однако, если вы добавите условие: ваши оценки по китайскому языку и оценки по математике будут ограничивать друг друга. В этом случае, очевидно, самый высокий общий балл, который вы можете получить за тест, не достигнет общего балла, и вы получите неправильный результат по идее только что. Поскольку подзадачи не являются независимыми, баллы по китайскому языку и математике не могут быть оптимальными одновременно, поэтому оптимальная подструктура разрушается. Обратите внимание на мой публичный аккаунт labuladong, чтобы увидеть больше замечательных статей об алгоритмах.
Возвращаясь к проблеме сбора сдачи, очевидно, что подзадачи не ограничивают друг друга, а независимы друг от друга. Таким образом, это уравнение перехода состояния может дать правильный ответ.
После этого нет никакой сложности, достаточно написать насильственный рекурсивный алгоритм по уравнению.
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
int ans = INT_MAX;
for (int coin : coins) {
// 金额不可达
if (amount - coin < 0) continue;
int subProb = coinChange(coins, amount - coin);
// 子问题无解
if (subProb == -1) continue;
ans = min(ans, subProb + 1);
}
return ans == INT_MAX ? -1 : ans;
}
Нарисуйте дерево рекурсии:
Анализ временной сложности: общее количество подзадач x время на подзадачу. Общее количество подзадач — это количество узлов рекурсивного дерева, которое трудно увидеть, оно равно O(n^k), короче говоря, оно экспоненциально. Каждая подзадача содержит цикл for со сложностью O(k). Таким образом, общая временная сложность составляет O (k * n ^ k), что является экспоненциальным.
2. Рекурсивный алгоритм с мемо
int coinChange(vector<int>& coins, int amount) {
// 备忘录初始化为 -2
vector<int> memo(amount + 1, -2);
return helper(coins, amount, memo);
}
int helper(vector<int>& coins, int amount, vector<int>& memo) {
if (amount == 0) return 0;
if (memo[amount] != -2) return memo[amount];
int ans = INT_MAX;
for (int coin : coins) {
// 金额不可达
if (amount - coin < 0) continue;
int subProb = helper(coins, amount - coin, memo);
// 子问题无解
if (subProb == -1) continue;
ans = min(ans, subProb + 1);
}
// 记录本轮答案
memo[amount] = (ans == INT_MAX) ? -1 : ans;
return memo[amount];
}
Без рисования очевидно, что «меморандум» сильно сокращает количество подзадач и полностью устраняет избыточность подзадач, поэтому общее количество подзадач не будет превышать суммы денег n, т. е. количество подзадач равно O(n). Время обработки подзадачи по-прежнему составляет O(k), поэтому общая временная сложность равна O(kn).
3. Динамическое программирование
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins)
if (coin <= i)
dp[i] = min(dp[i], dp[i - coin] + 1);
}
return dp[amount] > amount ? -1 : dp[amount];
}
окончательное резюме Если вы мало знаете о динамическом программировании, вы все равно можете увидеть это здесь. Я вам очень аплодирую. Я считаю, что вы освоили навыки проектирования этого алгоритма.
На самом деле, никаких фокусов для решения задач компьютером не существует, единственное решение — полностью исчерпать все возможности. Разработка алгоритма — это не что иное, как размышление о том, «как быть исчерпывающим», а затем поиск того, «как быть умным и исчерпывающим».
Перечислить уравнения динамического перехода — значит решить проблему «как быть исчерпывающим». Причина, по которой это сложно, заключается в том, что многие исчерпывающие методы необходимо реализовывать рекурсивно, а вторая причина заключается в том, что пространство решений некоторых проблем сложное, поэтому их исчерпывающее завершение нелегко.
Памятка и таблица DP направлены на то, «как быть умным и исчерпывающим». Идея использования пространства для времени — единственный способ уменьшить временную сложность Кроме того, что еще вы можете сделать?
2. Общая идея динамического программирования для решения игровых задач
Но головоломки в конце концов остаются головоломками, а настоящие алгоритмические задачи — это определенно не то, что можно решить случайно. Поэтому в этой статье используется игра в камни, чтобы рассказать о том, как использовать алгоритмы динамического программирования для решения таких задач, как «предположим, что два человека достаточно умны, и кто в конце концов победит».
Процедуры игровых задач аналогичны.Следующие примеры объясняются.Основная идея состоит в том, чтобы использовать кортежи для хранения результатов игры двух людей на основе двумерного dp. После освоения этого навыка, когда кто-то спросит вас о двух пиратах, делящихся драгоценными камнями, и о двух людях, держащих монеты, вы можете сказать другим: мне лень думать об этом, поэтому я могу просто написать алгоритм для вас, чтобы вы могли посчитать.
Наши изменения в «Игре камня» носят более общий характер:
Перед вами и вашим другом находится ряд каменных кучек, представленный массивом кучек, а кучки[i] — количество камней в i-й кучке. Вы по очереди берете камни, по одной стопке за раз, но только крайнюю левую или крайнюю правую стопку. После того, как все камни собраны, побеждает тот, у кого больше камней.
Количество кучек камней может быть любым положительным целым числом, а общее количество камней также может быть любым положительным целым числом, что может нарушить ситуацию победителя, сделавшего первый ход. Например, есть три кучки камней кучки = [1, 100, 3], независимо от того, возьмет ли первая рука 1 или 3, 100, которые могут решить исход, будут взяты второй рукой, и вторая рука выиграет.
Предполагая, что оба они умны, разработайте алгоритм, который возвращает разницу между последним счетом (общее количество камней) первой и второй руки. Например, в приведенном выше примере, если первый игрок получает 4 балла, а второй игрок получает 100 баллов, ваш алгоритм должен вернуть -96.
После этого продвижения эту задачу можно рассматривать как задачу сложного динамического программирования. Сложность игровой задачи в том, что два человека должны по очереди выбирать, и они оба хитрые, как запрограммировать этот процесс?
Я хотел бы подчеркнуть повторяющуюся рутину, сначала уточнить значение массива dp, а затем аналогично ряду торговых операций, пока вы найдете «статус» и «выбор», все будет сделано.
Сначала определите значение массива dp
Определение значения массива dp является очень техническим. Может быть несколько способов определить одну и ту же проблему. Различные определения приведут к различным уравнениям перехода состояний. Однако, пока нет проблем с логикой, один и тот же ответ может быть получено в итоге.
Предлагаю не зацикливаться на трюках и уловках, которые выглядят офигенно и короткий код, лучше быть стабильным и брать на вооружение дизайнерские идеи с лучшей интерпретируемостью и легче всего обобщаемые. В этой статье представлена общая схема проектирования игровых задач.
Прежде чем представить значение массива dp, давайте взглянем на окончательный вид массива dp:
В следующем объяснении кортеж считается классом, содержащим первое и второе свойства, и для экономии места эти два свойства обозначаются аббревиатурами fir и sec. Например, согласно данным на рисунке выше, мы говорим dp[1][3].fir = 10, dp[0][1].sec = 3.
Чтобы ответить на несколько вопросов, которые могут задать читатели:
Кортежи хранятся в этой двумерной таблице dp.Как их представить программно? Половина этой таблицы dp вообще не используется, как ее оптимизировать? Это очень просто, не беспокойтесь об этом, еще не поздно поговорить об идее решения проблемы в первую очередь.
Вот объяснение того, что означает массив dp:
dp[i][j].fir 表示，对于 piles[i...j] 这部分石头堆，先手能获得的最高分数。
dp[i][j].sec 表示，对于 piles[i...j] 这部分石头堆，后手能获得的最高分数。
举例理解一下，假设 piles = [3, 9, 1, 2]，索引从 0 开始
dp[0][1].fir = 9 意味着：面对石头堆 [3, 9]，先手最终能够获得 9 分。
dp[1][3].sec = 2 意味着：面对石头堆 [9, 1, 2]，后手最终能够获得 2 分。
Ответ, который нам нужен, это разница между окончательным счетом первой и второй рук, согласно этому определению, это dp[0][n-1].fir - dp[0][n-1].secdp [0][n−1 ].fir−dp[0][n−1].sec, то есть разность между лучшим результатом первого игрока и лучшим результатом второго игрока перед лицом всей геморрой.
2. Уравнение перехода состояния
Написать уравнения перехода между состояниями очень просто: сначала нужно найти все «состояния» и «выборы», которые может сделать каждое состояние, а затем выбрать лучшее.
Согласно предыдущему определению массива dp,Очевидно, есть три состояния: начальный индекс i, конечный индекс j и текущий ход.
dp[i][j][fir or sec]
其中：
0 <= i < piles.length
i <= j < piles.length
Для каждого состояния задачи есть два варианта: выбрать самую левую кучу камней или выбрать самую правую кучу камней. Мы можем исчерпывающе перечислить все состояния следующим образом:
n = piles.length
for 0 <= i < n:
for j <= i < n:
for who in {fir, sec}:
dp[i][j][who] = max(left, right)
Вышеупомянутый псевдокод является грубой основой для динамического программирования, и в задаче о серийных рядах есть похожие псевдокоды. Трудность этого вопроса в том, что оба выбирают попеременно, то есть выбор первого движителя повлияет на второго движителя Как это выразить?
Согласно нашему определению массива dp, эту трудность легко решить,Напишите уравнение перехода состояния:
dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
dp[i][j].fir = max(选择最左边的石头堆, 选择最右边的石头堆)
# 解释：我作为先手，面对 piles[i...j] 时，有两种选择：
# 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j]
# 但是此时轮到对方，相当于我变成了后手；
# 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1]
# 但是此时轮到对方，相当于我变成了后手。
if 先手选择左边:
dp[i][j].sec = dp[i+1][j].fir
if 先手选择右边:
dp[i][j].sec = dp[i][j-1].fir
# 解释：我作为后手，要等先手先选择，有两种情况：
# 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j]
# 此时轮到我，我变成了先手；
# 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1]
# 此时轮到我，我变成了先手。
В соответствии с определением массива dp мы также можем найти базовый случай, который является самым простым:
dp[i][j].fir = piles[i]
dp[i][j].sec = 0
其中 0 <= i == j < n
# 解释：i 和 j 相等就是说面前只有一堆石头 piles[i]
# 那么显然先手的得分为 piles[i]
# 后手没有石头拿了，得分为 0
Здесь следует отметить одну вещь: мы обнаружили, что базовый случай наклонен, и нам нужно использовать dp[i+1][j] и dp[i][j-1] при вычислении dp[i][j]:
Таким образом, алгоритм может не просто обходить массив dp построчно, аОбходим массив по диагонали:
Честно говоря, легко сказать, как пройти двумерный массив по диагонали, но вы действительно не можете понять, как это реализовать.Если вы мне не верите, подумайте об этом? Перечислены такие хитроумные уравнения перехода состояний.Если вы не можете написать код для их реализации, это действительно смущает. . .
3. Реализация кода
Как реализовать этот кортеж fir и sec, вы можете использовать python с его собственным типом кортежа, или использовать парный контейнер C++, или использовать трехмерный массив dp[n][n][2], последнее измерение эквивалентно tuple; или мы сами пишем класс Pair:
class Pair {
int fir, sec;
Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec;
}
}
Затем мы можем напрямую перевести наше уравнение перехода состояния в код.Можно обратить внимание на умение обхода массива по диагонали:
/* 返回游戏最后先手和后手的得分之差 */
int stoneGame(int[] piles) {
int n = piles.length;
// 初始化 dp 数组
Pair[][] dp = new Pair[n][n];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
dp[i][j] = new Pair(0, 0);
// 填入 base case
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// 斜着遍历数组
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
// 先手选择最左边或最右边的分数
int left = piles[i] + dp[i+1][j].sec;
int right = piles[j] + dp[i][j-1].sec;
// 套用状态转移方程
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i+1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j-1].fir;
}
}
}
Pair res = dp[0][n-1];
return res.fir - res.sec;
}
Метод решения динамического программирования без руководства уравнением перехода состояния абсолютно запутан, но, согласно предыдущему подробному объяснению, читатель должен быть в состоянии ясно понять смысл этого большого фрагмента кода.
Кроме того, обратите внимание, что вычисление dp[i][j] зависит только от элементов слева и под ним, поэтому должно быть место для оптимизации Преобразование в 1D dp, представьте, что вы сжимаете 2D-плоскость, то есть проецируете ее. до 1Д. Однако одномерный dp сложнее и имеет плохую интерпретируемость, поэтому вам не нужно тратить время на его понимание.
В-четвертых, окончательный итог
В этой статье представлено решение динамического программирования для решения игровых задач. Предпосылка проблемы игры, как правило, между двумя умными людьми.Общий метод программирования для описания этой игры представляет собой двумерный массив dp, в котором кортежи используются для представления оптимальных решений двух людей.
Причина такой схемы заключается в том, что после того, как первый ходок делает выбор, он становится вторым ходом, а второй ход становится первым ходом после того, как противник сделал выбор. Это переключение ролей позволяет нам повторно использовать предыдущие результаты, типичный признак динамического программирования.
Друзья, которые читают это, должны быть в состоянии понять процедуры алгоритмов для решения игровых задач. При изучении алгоритмов вы должны обращать внимание на структуру шаблона алгоритма, а не на какие-то идеи, которые кажутся потрясающими, и не рассчитывайте написать оптимальное решение. Не стесняйтесь использовать лишнее пространство, не пытайтесь преждевременно оптимизировать, не бойтесь многомерных массивов. Массив dp предназначен для хранения информации, чтобы избежать повторных вычислений и использовать ее небрежно, пока мы не будем удовлетворены.
3. Методы разработки динамического программирования: индуктивные идеи
Я понимаю рутину динамического программирования, и я не могу написать уравнение перехода состояния. У меня нет идей. Что мне делать? В этой статье используется «самая длинная возрастающая подпоследовательность», чтобы рассказать об общем методе разработки динамического программирования: идее математической индукции.
Самая длинная возрастающая подпоследовательность (сокращенно LIS) — относительно классическая задача. Легче придумать решение динамического программирования. Временная сложность — O(N^2). Мы используем эту задачу, чтобы объяснить, как писать от более мелкого к более мелкому. более глубокое динамическое программирование. Что сложнее придумать, так это использовать бинарный поиск, временная сложность O (NlogN), мы используем простую карточную игру, чтобы помочь понять это гениальное решение.
Сначала посмотрите на заголовок, его легко понять:
Обратите внимание на разницу между существительными "подпоследовательность" и "подстрока". Подстроки должны быть последовательными, но подпоследовательности не обязательно являются последовательными. Давайте сначала шаг за шагом разработаем алгоритм динамического программирования, чтобы решить эту проблему.
Решение для динамического программированияОсновная идея дизайна динамического программирования заключается в том,Математическая индукция.
Я полагаю, что все знакомы с методом математической индукции и изучали его в средней школе, а идея очень проста. Например, если мы хотим доказать математический вывод, то мы сначала предполагаем, что этот вывод верен, когда k Точно так же, когда мы разрабатываем алгоритм динамического программирования, разве нам не нужен массив dp? Мы можем предположить, что dp[0...i-1]dp[0...i−1] уже вычислены, и спросить себя: как мы можем вычислить dp[i] по этим результатам? Возьмите задачу о самой длинной возрастающей подпоследовательности непосредственно в качестве примера, и вы поймете. Однако прежде всего необходимо четко определить смысл массива dp, то есть что представляет собой значение dp[i]? Наше определение таково: dp[i] представляет собой длину самой длинной возрастающей подпоследовательности, заканчивающейся числом nums[i]. Два примера: Процесс эволюции алгоритма выглядит следующим образом: Согласно этому определению, наш окончательный результат (максимальная длина подпоследовательности) должен быть максимальным значением в массиве dp. Читатели могут спросить, результат каждого dp[i] в процессе — это то, что мы можем видеть невооруженным глазом, как мы должны разработать логику алгоритма для правильного вычисления каждого dp[i]? Это изюминка динамического программирования.Чтобы подумать о том, как выполнять переходы между состояниями, здесь можно использовать идею математической индукции: Мы уже знаем все результаты dp[0...4]dp[0...4], как мы можем вывести dp[5]dp[5] из этих известных результатов? В соответствии с нашим только что определением массива dp, мы теперь хотим найти значение dp[5], то есть мы хотим найти самую длинную возрастающую подпоследовательность, оканчивающуюся на nums[5]. nums[5] = 3, так как это возрастающая подпоследовательность, нам нужно только найти предыдущие подпоследовательности, чьи окончания меньше 3, а затем соединить 3 с концом, чтобы сформировать новую возрастающую подпоследовательность, и длину этой новой подпоследовательности плюс один. Конечно, может быть сформировано много новых подпоследовательностей, но нам нужна только самая длинная подпоследовательность, и длина самой длинной подпоследовательности принимается за значение dp[5]. Логика этого кода может вычислять dp[5]. На данный момент мы в основном закончили с этой проблемой алгоритма. Читатели могут спросить, мы только что вычислили dp[5], как мы вычисляем dp[4], dp[3]? Подобно математической индукции, вы уже можете вычислить dp[5], а остальное можно вычислить: Есть еще одна деталь: весь массив dp должен быть инициализирован 1, потому что подпоследовательность должна содержать как минимум себя, поэтому минимальная длина равна 1. Давайте посмотрим на полный код: На данный момент эта проблема решена, и временная сложность составляет O(N^2). Кратко о динамическом программированииПоток проектирования: Сначала уточните значение данных, хранящихся в массиве dp.. Этот шаг очень важен, и если он не сделан должным образом или недостаточно ясен, он будет мешать последующим шагам. Затем в соответствии с определением массива dp используйте идею математической индукции, предполагая, что dp[0...i-1]dp[0...i−1] известны, найдите способ найти dp[i]dp[i], как только этот шаг будет завершен, вся проблема в основном решаемо. Но если этот шаг не может быть выполнен, вероятно, определение массива dp недостаточно подходит, и значение массива dp необходимо переопределить; или информации, хранящейся в массиве dp, недостаточно для вывода следующего. ответ, и массив dp должен быть расширен в двумерные массивы или даже трехмерные массивы. Наконец, подумайте о том, каков базовый случай проблемы, чтобы инициализировать массив dp, чтобы обеспечить корректную работу алгоритма. Этот блог представляет собой перепечатку, чтобы лучше понять динамическое программирование.
Спасибо оригинальному автору, ниже приведена ссылка.int res = 0;
for (int i = 0; i < dp.size(); i++) {
res = Math.max(res, dp[i]);
}
return res;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
Резюме и ссылки
резюме
использованная литература