содержание
首先，先大致列下这篇文章会讲到什么
1.相较于暴力解法，动态规划带给我们的是什么？为什么会有重叠子问题以及怎么去避免的?
2.用不同难度的动态规划问题举例说明， 最后会使用《打家劫舍》系列三个题再重温一次.
一、动态规划带给我们的优势
传统递归 vs. DP
1. 先 递归解决
2. 后 动态规划解决
3. 动态规划 + 优化
二、动态规划四大解题步骤处理问题
步骤一：定义dp数组的含义
步骤二：定义状态转移方程
步骤三：初始化过程转移的初始值
步骤四：可优化点(可选)
案例一：打家劫舍I 「来自leetcode198」
步骤一： 定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例二：不同路径「来自leetcode62」
步骤一：定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例三：不同路径II 「来自leetcode63」
步骤一：定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例四：打家劫舍II 「来自leetcode213」
步骤一： 定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化设定
步骤四：优化
案例五：打家劫舍III 「来自leetcode337」
步骤一： 定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化设定
Динамическое программирование — ультра подробная серия
Эта статья длинная и более подробно развивает идею динамического программирования. Пожалуйста, наберитесь терпения и следите за идеями.
Динамическое программирование — ультра подробная серия
динамическое программирование, что всегда звучало как непостижимая алгоритмическая идея. Особенно на первом уроке алгоритма в школе учитель Барабала перечислил множество основных идей алгоритма,Жадное, возвратное, динамическое программирование..., я начал чувствовать, что мне нужно с легкостью решать всевозможные проблемы в мире алгоритмов, но я не ожидал, что после того, как я выучил это в оцепенении, я действительно выучил это (курсы в университете действительно Посмотрите). Только позже я понял, что университетские курсы — это, как правило, вводные объяснения, которые используются для расширения кругозора.Если вы действительно хотите иметь собственное мнение, вы должны много работать за кулисами, чтобы сформировать свое собственное.логика мышления.
А потом оглядываясь назад,динамическое программированиеДо сих пор сложно понять, что?Перекрывающиеся подзадачи, уравнения динамического перехода, точки оптимизацииПодождите, подождите и т. д., я был в замешательстве, и, наконец, я понял боль, посмотрел на чужой обмен и понял часть, и лихорадочно написал десятки вопросов. В основном он способен заблокировать Будду и убить Будду.
В процессе моего обучения и накопления, я надеюсь, что смогу вам немного помочь.Я верю, что прочитав эту статью, вы почувствуетединамическое программированиеЗамечательные вещи принес вам. должно быть правильнодинамическое программированиесформировать свой собственныйспособ мышления, Очень ? DP! ! !
Прежде всего, давайте обозначим, о чем пойдет речь в этой статье.
1. Что нам дает динамическое программирование по сравнению с методом полного перебора? Почему существуют перекрывающиеся подзадачи и как их избежать?
2. В качестве примера используйте задачи динамического программирования различной сложности и, наконец, повторите три вопроса из серии «Семейное ограбление».
После прочтения этой статьи, я полагаю, что у всех появится предварительное представление о проблеме DP, и она обязательно приступит к работе. Позже вы можете продолжить практиковать связанные вопросы, практика делает совершенным, и чем больше вы думаете, тем больше вы формируете свою собственную логику мышления.
Ладно, без лишних слов, приступим...
1. Преимущества динамического программирования
Это очень интересно, вы должны прочитать это, должно быть что-то получить, давайте! ???
Обычно в процессе разработки нашего алгоритма основное внимание уделяется эффективности выполнения алгоритма и эффективности использования пространства.
Это то, что мы знаемвременная сложность(время, необходимое для выполнения) икосмическая сложность(Длина единицы хранения, занятой во время выполнения)
Затем используйтевременная сложность и пространственная сложностьоценитьтрадиционный дизайн алгоритмаи использоватьидея динамического программированияСитуация с эффективностью находится в стадии решения
Традиционная рекурсия против DP
Возьмем пример, который большие парни назвали плохим?, этот каштан плохой, но он действительно плохойхороший запах: необходимо сосредоточиться наПодчеркивать.
N-й член последовательности Фибоначчи
**Причины рекомендации:** На мой взгляд, Фибоначчи — это случай начального уровня в дизайне динамического программирования, точно так же, как сказать «привет, мир» в программировании или «количество слов» в больших данных.
Фибоначчи интерпретирует это почти идеально.Идеи и приемы из динамического программированияОднако без каких-либо других нюансов этот очень четкий подход, кажется, хорошо согласуется с общим мышлением динамического программирования и с вводным подходом.
Далее рассмотрим тему:
写一个函数，输入n，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
Сравните решение между традиционным рекурсивным решением и идеей динамического программирования.
1. Сначала решить рекурсивно
Традиционный подход к такого рода проблемам состоит в том, чтобы использовать рекурсию для ее решения.Это относительно просто сделать, то есть непрерывно вызывать рекурсивно, см. следующий код:
class Solution(object):
i = 0
def fib_recur(self, N):
print "F(",self.i,") = ", N # 此处仅仅来看递归输出的N
self.i += 1
if N <= 1:
return N
return self.fib_recur(N-1) + self.fib_recur(N-2) # 递归输出
Результат вывода:
F( 0 ) = 4
F( 1 ) = 3
F( 2 ) = 2
F( 3 ) = 1
F( 4 ) = 0
F( 5 ) = 1
F( 6 ) = 2
F( 7 ) = 1
F( 8 ) = 0
Повторный расчет
Хорошо видно, что в процессе расчета всего 8 раз есть три пары одинаковых результатов расчета.Повторный расчет(элементы одного цвета на рисунке ниже не содержат серого), то есть в процессе рекурсии обрабатываются элементы, которые были рассчитаны.еще один перерасчет, это относительно низкая эффективность времени, единственное преимущество может заключаться в том, что код выглядит более понятным, но в конце концов это не лучший метод разработки алгоритма.
В коде при вычислении N идет рекурсивный расчетfib(N-1) + fib(N-2), то при вычислении в этом случае. Это будет процесс расчета на рисунке ниже.
Можно обнаружить, что будет значительная часть повторных вычислений, что является повторным потреблением времени.
Обратитесь к элементам одного цвета на рисунке, например, к розовому двойному счету, желтому двойному счету и т. д.
Примечание: пространство не увеличивается в рекурсии, оно всегда одинаковой длины, просто постоянно выталкивается и нажимается
Чтобы лучше проиллюстрировать неэффективность времени, вызванную этим повторным вычислением. Для другого примера, по сравнению с узлом расчета на приведенном выше рисунке, добавьте еще один узел для расчета и увеличьте расчет F(5), тогда из-за рекурсивного метода расчета будет больше элементов (деталь в проволочном каркасе в рисунок ниже) Повторные расчеты. в вычисленияхF(5), он будет рекурсивно вызыватьF(4)иF(3), а на рисунке ниже вычислениеF(4), он снова завершит расчетF(3). Таким образом, если N велико, затраты времени будут больше.
Таким образом, размер дерева удваивается, и временная сложность, очевидно, удваивается. Ужасно для времени.
Неэффективность, вызванная временной сложностью, серьезно перевешивает читабельность кода, поэтому мы можем найти способпрошлые расчетыпройденный узелсохранить. Таким образом, мы будем использовать экономию времени, привносимую идеей динамического программирования, о которой будет сказано ниже.
временная сложность:---> Экспоненциальный
Сложность пространства:
2. Решение для пост-динамического программирования
Кратко объясните буквальное значение:
Динамическое программирование:Мы не решаем проблему напрямую, а добиваемся оптимальной ситуации каждого шага при решении задачи на каждом шаге. Другими словами, на каждом этапе процесса решения проблемы используйтепрошлое состояниеа такжеТекущее состояниедостичь текущего оптимального состояния.
планирование:При решении таких задач вообще будет процесс "заполнения формы", будь то простой случайодномерная таблицаЕще немного сложнее2D стол, все сосвободить место для времениИдея для того, чтобы стремиться к наилучшей эффективности времени (сохранение промежуточного значения процесса, удобного для последующего непосредственного использования).
**Динамический:** Используя приведенный выше случай, каждый шаг в процессе рекурсивного решения будет решаться непрерывно, начиная с основной задачи «сверху вниз», и на каждом этапе будет повторяться одна и та же логика вычислений. По сравнению с рекурсивной идеей динамическое программирование повышает сохранность исторических результатов расчета, постепенно записывает промежуточные результаты расчета и на каждом шаге получает оптимальное значение.
Поэтому динамическое программирование позволяет избежать повторных вычислений и добиться оптимального времени, начиная сэкспоненциально становитсяПостоянный уровень очень ценен по сравнению с накладными расходами на открытие пространства памяти для хранения промежуточных значений процесса.
Тогда давайте решим Фибоначчи в соответствии с идеей динамического программирования
По правилам в заголовке:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), when N > 1
Тогда значение ??F(N) связано только с его первыми двумя состояниями??
А. Значение инициализации: F(0) = 0, F(1) = 1 б) Чтобы вычислить F(2), затем F(2) = F(0) + F(1) --> сохранить F(2) C. Чтобы вычислить F(3), затем F(3) = F(2) + F(1) --> сохранить F(3) г. Чтобы вычислить F(3), затем F(4) = F(3) + F(2) --> сохранить F(4)
Используя идею динамического программирования, реализованную Фибоначчи с помощью одномерных массивов, см. рисунок ниже
Не правда ли очень простая идея?Его можно достичь просто используя циклы только сохраняя некоторые значения в процессе.Нет необходимости использовать рекурсивные повторные вычисления для ее достижения.
Хотите посчитать, сколько энных значений вы получили? Итак, следующие пункты - это то, что мы должны сделать
а.определить одномерный массив---> Обычно именуется через dp
б.Настройки динамического уравнения---> F(N) в вопросе = F(N - 1) + F(N - 2)
в.Инициализировать значение---> F(0) = 0 и F(1) = 1
Приведенные выше пункты a, b и c являются основными элементами идеи динамического программирования.
Давайте посмотрим на код, который нужно реализовать (в коде используйте dp для замены вышеуказанного F())
class Solution(object):
def fib(self, N):
if N == 0:
return 0
dp = [0 for _ in range(N+1)] # 1定义dp[i]保存第i个计算得到的数值
dp[0] = 0 # 2初始化
dp[1] = 1 # 2初始化
for i in range(2, N+1): # 3动态方程实现，由于0和1都实现了赋值，现在需要从第2个位置开始赋值
dp[i] = dp[i - 1] + dp[i - 2]
print dp # 记录计算过程中的次数，与上述递归形成对比
return dp[N]
вывод:
[0, 1, 1, 2, 3]
3
Выше наиболее важным пунктом является 1 2 3, а процесс выполнения относится квыводПо сравнению с рекурсивным алгоритмом расчет выполняется намного меньше, и тот же расчет выполняется только один раз.
временная сложность:
Сложность пространства:
Вышеупомянутое содержание было введено, вот разделительная линия, для вышеуказанногоРекурсивный против DP
Поскольку схема динамического программирования также была введена, давайте подробнее рассмотрим, есть ли место для оптимизации.В конце концов, для разработки схемы алгоритма нужно найти точку оптимизации.Будь то время или эффективность пространства , мы хотим достичь идеального значения .
3. Динамическое программирование + оптимизация
Давайте посмотрим на эту диаграмму и обнаружим, что каждый вычислительный узел имеетотносится только к первым двум терминам. Другими словами, нам нужно сохранить только два значения, и при вычислении нового значения узла присвоить новое значение первому из двух предыдущих значений.
Говоря, что есть только два значения, теперь определим две переменные dp1 и dp2. Итак, теперь давайте смоделируем шаг за шагом:
А. Значение инициализации: F(0) = 0, F(1) = 1
б) Чтобы вычислить F(2), затем F(2) = F(0) + F(1) --> сохранить F(2)
Кстати, назначьте F(1) для dp1 и f(2) для dp2.
C. Чтобы вычислить F(3), затем F(3) = F(2) + F(1) --> сохранить F(3)
Кстати, назначьте F(2) на dp1, а F(3) на dp2.
г. Чтобы вычислить F(3), затем F(4) = F(3) + F(2) --> сохранить F(4)
Кстати, назначьте F(3) для dp1 и F(4) для dp2.
Пока что весь процесс использует только две переменные для хранения значений, сгенерированных в процессе, и была оптимизирована эффективность использования пространства, которая ранее не оптимизировалась.
Давайте также опубликуем код для справки
class Solution(object):
def fib_dp1(self, N):
if N == 0: return 0
dp1, dp2 = 0, 1
for i in range(2, N+1):
dp1 = dp1 + dp2
dp1, dp2 = dp2, dp1
return dp2
Не кажется ли это более лаконичным.
Я так много написал, сам того не осознавая.
Если некоторые читатели скажут, что это слишком просто, содержание этой статьи предназначено для новичка.Если читатель находится на среднем уровне, вы можете сразу перейти к следующему случаю 3, чтобы начать справку.
Кроме того, если у вас есть какие-либо комментарии, не стесняйтесь комментировать мою статью, добро пожаловать и спасибо за совместное обсуждение.
Как вы относитесь к этому примеру? Вот три момента:1. Определить массив dp 2. Динамическое уравнение 3. Инициализировать значение
Это также объясняет, почемуПоследовательность Фибоначчипредставлятьдинамическое программированиеДа, потому что сама последовательность Фибоначчи ясно говорит вам, что такое динамическое уравнение и каково инициализированное значение, поэтому вы можете хорошо прочувствовать эту идею, особенно от традиционной идеи рекурсии -> динамического программирования до оптимизации. С одной стороны, это стоит подумать.
Далее давайте найдем несколько репрезентативных каштанов, чтобы попробовать
Есть ли у вас чувство динамического программирования здесь?
Статья длинная, вы можете сначала подписаться на нее или добавить ее в закладки, или вы можете подписаться на «Экологию компьютерной рекламы», ответив «DP», чтобы получить pdf-файл этой статьи.
2. Четыре основных шага решения проблем в динамическом программировании для решения проблем
Вышеупомянутое использует проблему последовательности Фибоначчи, что приводит к следующим моментам, которые будут подробно описаны здесь.
В следующих случаях мы постараемся строго следовать этим шагам для решения проблемы.
Шаг 1: Определите значение массива dp
Шаг 2: Определите уравнение перехода состояния
Шаг 3: Начальное значение, переданное в процессе инициализации
Шаг 4: Оптимизируемые точки (необязательно)
Шаг 1: Определите значение массива dp
В большинстве случаев нам нужно определить одномерный массив или двумерный массив для хранения оптимального значения, сгенерированного в процессе вычисления.Почему здесь оптимальное значение? Именно потому, что в процессе решения задачи обычно используется массив dp для сохраненияОптимальное значение от начала до текущей ситуации, поэтому оптимальное значение до сих пор сохраняется, чтобы избежать повторных вычислений (студенты, которые, кажется, здесь запутались, подумайте о сравнении между рекурсивным решением Фибоначчи и динамическим программированием выше)
Следовательно, является ли dp одномерным или двумерным, необходимо знать, что оно представляет, вообще говоря, представляет собой оптимальное значение в текущей ситуации.
Шаг 2: Определите уравнение перехода состояния
Что такое уравнение динамического переноса? Если перед нами стоит проблема, то в процессе решения этой проблемы мы обнаружим, что есть много перекрывающихся подзадач и перекрывающихся подструктур, и за счет решения этих подзадач проблема в конечном итоге решить.
Говоря простым языком, в процессе решения задачи можно найти динамический закон, который постоянно решает подзадачи, например, F(N) = F(N - 1) + F(N - 2) по Фибоначчи, а в других В задачах, решаемых динамическим программированием, такие внутренние законы нам необходимо открывать самим. Это самое сложное и самое важное, пока этот шаг решен, то у нас в принципе не будет проблем с решением этой задачи.
Шаг 3: Начальное значение, переданное в процессе инициализации
Следуя идее шага 2, поскольку динамическое уравнение было определено, вам нуженвращатьсяподдеть его для постоянного расчета.
Ну, этовращатьсяНам нужно инициализировать определение, активировать динамическое уравнение и выполнить расчет. Например, F(0) = 0 и F(1) = 1 в Фибоначчи, с этими двумя значениями его динамическое уравнение F(N) = F(N - 1) + F(N - 2) может продолжаться.
Это начальное значение, о котором мы хотим подумать, и реальная проблема может по-прежнему требовать от нас ясного мышления.
Шаг 4: Оптимизируемые точки (необязательно)
Самое главное, что здесь можно оптимизировать — это массив dp, и для разных задач будут разные точки оптимизации.
В примере мы будем выполнять различные оптимизации.
Словом, рекомендуется больше рисовать и рисовать больше картинок, и постепенно будут появляться многие детали.
Дело 1: Ограбление I "От leetcode198"
Вы профессиональный вор, планирующий украсть дома вдоль улицы. В каждой комнате спрятана определенная сумма денег.Единственное ограничение, влияющее на вашу кражу, это то, что соседние дома оборудованы взаимосвязанными противоугонными системами.Если воры взломают два соседних дома в одну и ту же ночь, система сработает. автоматическая сигнализация.
Учитывая массив неотрицательных целых чисел, представляющих сумму, хранящуюся в каждом доме, рассчитайте максимальную сумму, которую вы можете украсть, не активировав тревогу.
Пример 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
Пример 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
Давайте разделим классическую серию дел и обсудим ее. Давайте сначала посмотрим на «Семейное ограбление I».
Причина, по которой эту проблему можно решить с помощью идеи динамического программирования, заключается в том, что в процессе кражи предмет, который вор всегда хочет украсть, является наиболее ценным и оптимальным, и каждый шаг связан с предыдущей ситуацией кражи. , и каждый шаг должен учитывать, можно ли его украсть и принесет ли он наибольшую пользу, что позволяет использовать для решения задачи идею динамического программирования. Затем выполните четыре шага, чтобы решить проблему.
Шаг 1: Определите значение массива dp
Как упоминалось ранее, значение, хранящееся в массиве dp, обычно представляет собой оптимальное значение на данный момент.В этом разделе мы определяем:
dp[i] представляет наибольшую сумму, украденную из i-го дома, которая является текущей максимальной суммой подзаказа.
Неважно, сколько домов, в итоге мы получаем последнее значение массива dp, чтобы получить максимальную сумму, украденную вором.
Шаг 2: Найдите динамическое уравнение между реляционными элементами
Проблема, решаемая с помощью динамического программирования, обычно заключается в решении оптимальной подзадачи «сверху вниз» для непрерывного вычисления оптимального значения каждого шага.
То есть, чтобы получить значение dp[i], мы должны знать оптимальное значение каждого шага dp[i-1], dp[i-2], dp[i-3] ..., в этом В процессе перехода состояния мы должны выяснить, как определить реляционное выражение. Однако на каждом шаге расчета оно имеет связь с предыдущими элементами.Эта фиксированная связь представляет собой перекрывающуюся подзадачу, которую мы ищем, а также динамическое уравнение, которое будет подробно определено далее.
В этой задаче, когда вор приходит в i-й дом, у него есть два варианта: один — воровать, другой — не воровать, а затем выбрать тот, который имеет большую ценность.
а. Расчет случая кражи: должно быть dp[3] = nums[2] + dp[1]. Если дом украден, соседний дом нельзя украсть. Поэтому общий термин: dp[ i] = число [i-1] + дп [i-2]
б. Расчет без кражи: должно быть dp[3] = dp[2]. Если дом не украден, то соседний дом является его оптимальным значением. Следовательно, общий термин: dp[i ] = dp[i -1]
Наконец, если вы хотите украсть наибольшую сумму, то максимальное значение между кражей и не кражей должно быть выбрано в качестве ключевого момента того, выбираем ли мы. который:
Динамическое уравнение: dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
Шаг 3: Инициализируйте числовые настройки
Инициализация: Дайте dp позицию, когда дома нет, а именно: dp[0] 1 Когда size=0, дома нет, dp[0]=0; 2 Когда size=1, есть дом, просто украдите его: dp[1]=nums[0]
Итак, организуйте код в соответствии с этой идеей:
class Solution(object):
def rob(self, nums):
# 1.dp[i] 代表当前最大子序和
# 2.动态方程: dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
# 3.初始化: 给没有房子时，dp一个位置，即：dp[0]
# 3.1 当size=0时，没有房子，dp[0]=0；
# 3.2 当size=1时，有一间房子，偷即可：dp[1]=nums[0]
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size+1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, size+1):
dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
return dp[size]
Временная сложность: O(N)
Пространственная сложность: O(N)
Тогда подумайте и посмотрите, есть ли место для оптимизации, и постарайтесь максимально высвободить некоторые ресурсы компьютера.
Шаг 4: Оптимизируйте
Из соотношения dp[i] = max(dp[i-1], nums[i-1]+dp[i-2]) каждое динамическое изменение связано с двумя предыдущими состояниями (dp[i-1 ]+dp[i-2]) i-1], dp[i-2]), а некоторые из предыдущих значений не нужны.
Следовательно, dp нужно определить только две переменные, уменьшая сложность пространства до O (1)
class Solution(object):
def rob_o(self, nums):
# 依照上面的思路，其实我们用到的数据永远都是dp的dp[i-1]和dp[i-2]两个变量
# 因此，我们可以使用两个变量来存放前两个状态值
# 空间使用由O(N) -> O(1)
size = len(nums)
if size == 0:
return 0
dp1 = 0
dp2 = nums[0]
for i in range(2, size+1):
dp1 = max(dp2, nums[i-1]+dp1)
dp1, dp2 = dp2, dp1
return dp2
Временная сложность: O(N)
Космическая сложность: O(1)
После разговора о «Семейном ограблении I» в середине вкраплена еще одна тема, проблема, решаемая с помощью двумерного дп.
Наконец, давайте поговорим о «Семейном ограблении II» и «Семейном ограблении III».ограблениеПроблема понятна, я полагаю, что у вас есть более глубокий опыт входа в динамическое программирование.
Если некоторые читатели скажут, что это слишком просто, содержание этой статьи предназначено для новичка.Если читатель находится на среднем уровне, вы можете сразу перейти к следующему случаю 3, чтобы начать справку.
Кроме того, если у вас есть какие-либо комментарии, не стесняйтесь комментировать мою статью, добро пожаловать и спасибо за совместное обсуждение.
Случай 2: разные пути "от leetcode62"
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
В. Сколько всего существует различных путей?
Пример 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
Пример 2:
输入: m = 7, n = 3
输出: 28
намекать:
1
Следующие четыре шага все еще обсуждаются:
Шаг 1: Определите значение массива dp
Текущий вопрос из верхнего левого угла в нижний правый угол Вопрос предусматривает, что вы можете идти только вправо или вниз, поэтому мы должны определить двумерный массив для сохранения значений в процессе расчета. Итак, это определение блока:
dp[i][j]: представляет общее количество всех путей к позиции (i, j)
То есть: сумма всех путей робота из левого верхнего угла в правый нижний угол, значение каждой позиции в dp представляет собой общее количество путей для достижения каждой позиции (i, j)
Шаг 2: Найдите динамическое уравнение между реляционными элементами
Поскольку в вопросе указано, что он может двигаться только вправо или вниз, когда робот движется, он может двигаться только вправо или вниз.
Затем отдельно обсудите следующие два случая: если вы хотите достичь позиции (i, j), вы можете начать с позиции (i-1, j) или (i, j-1). Следовательно, общее количество путей к позиции (i, j) должно бытьКоличество путей для достижения позиции (i-1, j) + Количество путей для достижения позиции (i, j-1). Итак, теперь можно определить динамические уравнения:
Динамическое уравнение: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Шаг 3: Инициализируйте числовые настройки
Очевидно, что когда робот проходит 0-ю строку и 0-й столбец, как бы он ни шел, есть только один способ движения.
Следовательно, настройка значения инициализации должна быть такой, что dp[0..m][1] или dp[1][0..n] равны 1
Итак, начальные значения следующие:
дп[0] [0….n-1] = 1;// Робот идет до упора вправо, а 0-й столбец - все 1
дп[0…м-1][0] = 1;// Робот идет до конца, а 0-й столбец - все 1
Теперь организуйте код в соответствии с этой идеей.
class Solution(object):
def uniquePaths1(self, m, n):
# 初始化表格，由于初始化0行 0列都为1。那么，先全部置为1
dp = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n-1][m-1]
В приведенном выше коде, поскольку dp[0..m][1] или dp[1][0..n] равны 1, при определении двумерного массива dp начальное значение присваивается 1
Затем начните с позиции (1, 1) и подсчитайте общее количество путей для каждой позиции.
Временная сложность: O(M*N)
Пространственная сложность: O(M*N)
Теперь, когда мы здесь, давайте подумаем об этом и посмотрим, можно ли что-то оптимизировать.
Шаг 4: Оптимизируйте
В соответствии с предыдущими идеями решения также должна быть возможность оптимизировать пространство.
Ссылаясь на предыдущий случай, ранее был определен одномерный массив dp.Точка оптимизации заключается в том, что каждый шаг связан только с двумя предыдущими вычисленными значениями, а затем точкой оптимизации является dp[N] -> dp1 и dp2 , Сложность пространства составляет от O (N) -> O (1).Если это крупномасштабный расчет данных, эффективность использования пространства значительно повышается.
Теперь динамическое уравнение в этом примереdp[i][j] = dp[i-1][j] + dp[i][j-1], ясно, что значение состояния на каждом шаге связано только со значением, примыкающим слева, и значением выше. Пример (для удобства используйте 3*4 в качестве примера):
В этом полном описании изображения робот начинает двигаться из положения (1, 1) в верхнем левом углу и постепенно продвигается на каждый шаг в соответствии с динамическим уравнением.Четко видно, что каждый раз, когда робот перемещает сетку , полученный общий путь будет таким же, как связаны его верхнее и левое значения. То есть мы обнаружим, что при перемещении робота на строку 2 данные в строке 0 совершенно бесполезны.
Следовательно, эта точка оптимизации выходит.При разработке алгоритма dp определяет только массив из 2 строк и N столбцов, что нормально, экономя пространство на m-2 строки. Если вы хотите понять этот код, спроектируйте его самостоятельно, у вас будет более глубокое понимание, когда вы напишете его самостоятельно, а затем подчеркните: больше думайте и формируйте тонкий образ мышления.
После прочтения этого шага, является ли это очевидным моментом оптимизации?Почему код не для всех приведен выше? Это потому, что я вижу точку, которую, кажется, можно продолжать оптимизировать (придерживаясь пункта оптимизации пространства, хахаха), а затем продолжать поднимать шум из-за накладных расходов.
**Указание: **Согласно нашему плану оптимизации выше, сказано, что «когда робот перемещается во вторую строку, данные в 0-й строке совершенно бесполезны», на самом деле об этом думают нынешние умные читатели, а затем посмотрите на него, изображение ниже (взято из изображения выше). На самом деле, мало того, что 0-я строка совершенно бесполезна, так еще и при переходе второй строки в позицию (i,j) вычисляется позиция (i,j), затем вычисляется позиция (i,j). 1, к) данные также бесполезны. Другими словами, при обходе некоторые данные, начинающиеся в строке 1, бесполезны и все равно занимают место.
Мы должны больше думать об этом, больше понимать и рисовать больше картинок.
Следуя этой идее, посмотрите на шаги на рисунке ниже и нарисуйте одномерный массив для решения задачи, а также нарисуйте процесс аналогии между каждым шагом и рисунком выше:
Здесь сонливые ученики могут сами нарисовать картинку и понять ее.Личное ощущение - хорошее расширение мышления.
Далее следуйте этой идее, чтобы реализовать код, и вы обнаружите, что код очень прост.
class Solution(object):
def uniquePaths2(self, m, n):
if m > n:
m, n = n, m
dp = [1 for _ in range(m)]
for i in range(1, n):
for j in range(1, m):
dp[j] = dp[j] + dp[j-1]
return dp[m-1]
Временная сложность: O(m*n)
Пространственная сложность: O(min(m,n))
Это намного проще и чище с точки зрения мышления?
После того, как мы разобрались с каштанами выше, мы сделаем приведенный выше пример задачи простым повышением сложности, грубо говоря, столкновением с несколькими препятствиями на дороге.
Проверьте это:
Случай 3: Другой путь II "От leetcode63"
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
Теперь учтите, что в сетке есть препятствия. Итак, сколько различных путей будет из верхнего левого угла в нижний правый угол?
Объяснение: значения m и n не превосходят 100.
Пример 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
Давайте сначала рассмотрим два ключевых момента вопроса:Ключевой момент 1: только вправо или вниз Ключевая точка 2: 1, если есть препятствие, 0, если препятствия нет
Согласно ключевому пункту 1 и ключевому пункту 2 обсуждение по-прежнему проходит в четыре этапа:
Шаг 1: Определите значение массива dp
Массив dp, определенный в этом вопросе, имеет то же значение, что и массив dp, определенный в предыдущем примере, но поскольку в этом вопросе уже определен массив препятствияGrid, его можно использовать напрямую, не открывая дополнительное пространство. Затем используйте препятствияGrid в качестве оптимального значения в процессе расчета хранилища в динамическом программировании.
Шаг 2: Найдите динамическое уравнение между реляционными элементами
Ссылаясь на предыдущую задачу, задайте уравнение динамики: Сетка-препятствие[i][j] = Сетка-препятствие[i-1][j] + Сетка-препятствие[i][j-1] Так как в процессе движения робот имеет препятствия, то к приведенному выше динамическому уравнению необходимо добавить некоторые ограничения А. Если текущая решетка препятствий[i][j] равна 0. Затем непосредственно рассчитать процесс расчета по динамическому уравнению б) если текущая препятствияGrid[i][j] не равна 0. Затем напрямую установите значение этой позиции на 0
Следовательно, при прохождении динамического уравнения сначала оценивается сетка препятствий[i][j], а затем вычисляется и выполняется динамическое уравнение.
Шаг 3: Инициализируйте числовые настройки
По сравнению с предыдущим вопросом сходство в том, что когда робот проходит 0-ю строку и 0-й столбец, независимо от того, как он идет, есть только один способ движения. Но поскольку есть препятствия, когда вы достигаете препятствия, вы не можете обойти его (первая линия используется в качестве примера на рисунке ниже).
Следовательно, при инициализации строки 0 и столбца 0 объекты за препятствием 1 недоступны. Итак, инициализируем логическое представление строк и столбцов:
Достижима ли позиция = статус предыдущей позиции и достижима ли позиция Получить, может ли эта позиция быть достигнута
Только когда предыдущее положение равно 1 (достижимо, только 1 путь) и текущее положение равно 0 (нет препятствия), можно достичь положения, а затем установить 1 для этого положения (достижимо, только 1 способ)
# 0 行初始化表达式:
obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] == 1)
# 0 列初始化表达式:
obstacleGrid[clo][0] = int(obstacleGrid[clo][0] == 0 and obstacleGrid[clo-1][0] == 1)
После того, как они будут готовы, кодируйте в соответствии с соответствующими идеями.
class Solution(object):
def uniquePathsWithObstacles1(self, obstacleGrid):
# 行列长度
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# 如果在位置(0, 0)，哪里都去不了，直接返回0
if obstacleGrid[0][0] == 1:
return 0
# 否则，位置(0, 0)可以到达
obstacleGrid[0][0] = 1
# 初始化 0 列
for clo in range(1, m):
obstacleGrid[clo][0] = int(obstacleGrid[clo][0] == 0 and obstacleGrid[clo-1][0] == 1)
# 初始化 0 行
for row in range(1, n):
obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] == 1)
# 从位置(1, 1)根据动态方程开始计算
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
else:
obstacleGrid[i][j] = 0
return obstacleGrid[m-1][n-1]
Временная сложность: O(mxn)
Космическая сложность: O(1)
Шаг 4: Оптимизируйте
Не будем говорить об оптимизации этого куска, смысла оптимизации здесь в принципе нет, раньше это было из-за необходимости освободить место в памяти и оптимизировать пространство, эта проблема заключается в работе в заданном массиве.
После того, как у нас будет основа этих дел, мы обсудим оставшиеся две темы классической серии «Семейное ограбление», а затем подойдем к концу.Позже мы также надеемся общаться с вами по-разному и учиться у каждого разное.
Если некоторым читателям надоело смотреть, они могут сначала сохранить его, сохранить, а затем вернуться, чтобы просмотреть, переварив предыдущий контент.
Дело 4: Ограбление II "От leetcode213"
Вы профессиональный вор, планирующий украсть дома вдоль улицы, в каждом из которых спрятана определенная сумма денег. Все дома в этом месте расположены по кругу, что означает, что первый дом и последний дом находятся рядом друг с другом. В то же время соседние дома оборудованы взаимосвязанными противоугонными системами: если воры взломают два соседних дома в одну и ту же ночь, система автоматически подаст сигнал тревоги.
Учитывая массив неотрицательных целых чисел, представляющих сумму, хранящуюся в каждом доме, вычислите максимальную сумму, которую вы можете украсть, не активировав тревогу.
Пример 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
Пример 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
В отличие от «Семейного ограбления I», дом «Семейного ограбления I» является линейным, а «Семейное ограбление II» - круговым, поэтому количество рассматриваемых точек будет увеличиваться, поскольку первое место связано, мы делим его на следующие 3. установить следующие условия:
а) не воровать
б.
в) не занимать первое место Очевидно, что методы c теряют слишком много и не дадут наибольшей суммы, поэтому выберите a и b. Затем следующее делится на два случая, соответственно вычисляя два случая без головы и без хвоста, чтобы определить, каким образом вор крадет наибольшую сумму.
Следующее по-прежнему соответствует предыдущим четырем шагам для анализа
Шаг 1: Определите значение массива dp
dp[i] Значение такое же, как и раньше, значение, хранящееся в массиве dp, обычно представляет собой оптимальное значение на данный момент.
Итак,dp[i] представляет наибольшую сумму, украденную из i-го дома, которая является текущей максимальной суммой подзаказа.
но обсудим в концене включает первыйинет хвостаПоследняя цифра массива dp, полученная в этих двух случаях, а затем получаем большую, которая является наибольшей суммой, которую мы хотим получить
#####Шаг 2: Найдите динамическое уравнение между реляционными элементами
Динамическое уравнение см. в «Семье Цзеше I», где очень подробно описан процесс. Изменение динамического уравнения в этом примере точно такое же, как и раньше:
dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
Шаг 3. Инициализируйте настройки
Инициализация: Дайте dp позицию, когда дома нет, а именно: dp[0] а) при size=0 дома нет и вор не может его украсть: dp[0]=0; б) Когда size=1, есть дом, просто укради его: dp[1]=nums[0]
Так как первая часть дома связная, то при расчете она сразу делится на два случая. Первый пропускает первый дом, а второй пропускает второй дом, что приводит к двум результатам массива. Наконец, просто сравните размер последней цифры, и все в порядке. решать!
После шага 3 этого примера заинтересованные студенты могут сами написать код, который очень похож на код «Семейного ограбления I». Позже я написал оптимизированный код, который может быть более понятен в том, как его писать. Давайте перейдем непосредственно к шагу 4. В приведенном выше случае давайте посмотрим на оптимизированное решение:
Шаг 4: Оптимизируйте
Также из соотношения dp[i] = max(dp[i-1], nums[i-1]+dp[i-2]) каждое динамическое изменение связано с двумя предыдущими состояниями (dp[i- 1], dp[i-2]), а часть предыдущих значений сохранять не обязательно, достаточно сохранить две переменные для сохранения оптимального значения процесса.
В коде есть подробные комментарии:
class Solution(object):
def rob(self, nums):
# 点睛：与打家劫舍I的区别是屋子围成了一个环
# 那么，很明显可以分为三种情况：
# 1. 首位都不偷
# 2. 偷首不偷尾
# 3. 不偷首偷尾
# 显然，第1种方式损失太大，选取2、3。
# 那么，分为两种情况，分别计算不包含首和不包含尾这两种情况来判断哪个大哪个小
# 1.dp[i] 代表当前最大子序和
# 2.动态方程: dp[i] = max(dp[i-1] and , nums[i-1]+dp[i-2])
# 3.初始化: 给没有房子时，dp一个位置，即：dp[0]
# 3.1 当size=0时，没有房子，dp[0]=0；
# 3.2 当size=1时，有一间房子，偷即可：dp[1]=nums[0]
# 依照《打家劫舍I》的优化方案进行计算
# nums处理，分别切割出去首和去尾的子串
nums1 = nums[1:]
nums2 = nums[:-1]
size = len(nums)
if size == 0:
return 0
if size == 1:
return nums[0]
def handle(size, nums):
dp1 = 0
dp2 = nums[0]
for i in range(2, size+1):
dp1 = max(dp2, nums[i-1]+dp1)
dp1, dp2 = dp2, dp1
return dp2
res1 = handle(size-1, nums1)
res2 = handle(size-1, nums2)
return max(res1, res2)
Временная сложность: O(N)
Космическая сложность: O(1)
Посмотрите на ситуацию, с которой столкнулся вор ниже, и вздохните: даже если вы вор, вы должны планировать шаг за шагом, чтобы получить наибольшую сумму...
Дело 5: Ограбление III "От leetcode337"
В прошлый раз ограбив улицу и ряд домов, воры обнаружили новый район ограбления. В эту область есть только один вход, который мы называем «корень». Помимо «корня», к каждому дому подключен один и только один «родительский» дом. После некоторой разведки хитрый вор понял, что «все дома в этом месте устроены как бинарное дерево». Если в одну и ту же ночь будут ограблены два напрямую связанных дома, дома автоматически вызовут полицию.
Подсчитайте максимальную сумму, которую вор может украсть за одну ночь, не сработав сигнализации.
Пример 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
Пример 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
Название очень хорошее, но оно сразу дает людям какой-то кайф, на который вор не годится...
Ближе к делу, давайте сначала поговорим о самой теме
Вор в «Семейном ограблении» перешел от одномерного линейного к круглому, а затем к двухмерному прямоугольному дому? Я думаю, что это просто, просто высушите его в форме дерева, не правда ли, оно выглядит очень ароматным, и я очень хочу его прочитать, изучить...
Давайте разберем несколько идей, а затем выполним четыре шага:
1. Так как дом древовидный, мы можем пройти его, используя традиционный метод обхода дерева (по порядку, по порядку, последующий) 2. Простая идея состоит в том, чтобы пройти вверх по дереву, чтобы получить оптимальное значение грабежа. Последующий обход необязателен 3. Получите оптимальное значение каждого узла и, наконец, выберите оптимальный результат.
Все еще выполните три шага для анализа (без точки оптимизации)
Шаг 1: Определите значение массива dp
dp[i] представляет наибольший грабеж (получение наибольшего количества денег) для этого узла и ниже
Шаг 2: Найдите динамическое уравнение между реляционными элементами
Каждый раз, когда мы идем к узлу, будет две ситуации, то естьукрасть (1)ине воруй (0). Обсудим отдельно:
а) использоватьdp[0]Это означает, что узел пока не ворует больше всего денег, поэтому сын-узел может воровать или нет.
Итак:dp[0] = max(left[0], left[1]) + max(right[0], right[1])
б. использоватьdp[1]Если представитель украл больше всего денег из узла на данный момент, ни один из дочерних узлов не может быть украден.
Итак:dp[1] = value + left[0] + right[0](значение представляет значение узла)
Есть ли что-то, чего вы не понимаете? Тогда объясни это:
left[0] означает, что левый дочерний элемент не будет красть, чтобы получить максимальную сумму.
left[1] означает кражу левого потомка, чтобы получить наибольшую сумму
right[0] означает не воровать нужного потомка, чтобы получить наибольшую сумму
right[1] означает кражу правильного потомка, чтобы получить наибольшую сумму
Если вы все еще не понимаете, пожалуйста, оставьте сообщение или личное сообщение мне, чтобы связаться со мной и преследовать меня в любое время.
Шаг 3. Инициализируйте настройки
Инициализация этого примера относительно проста, то есть, когда форма текущего дерева пуста, напрямую возвращайте dp[0, 0]
Полный код размещен ниже, который содержитИнициализация дереваКод && куча комментариев:
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution():
def rob(self, root):
# 说明：
# 1.由于房屋是树状的，因此，我们可以使用遍历树的传统方法进行遍历(前序、中序、后续)
# 2.简单的思路是，从树低进行往上遍历，拿到最优的打劫值。可以选用后续遍历
# 3.得到每一节点的最优值，最后选取最优的结果
# 1.dp[i]代表该节点及以下拿到的最多的钱
# 2.动态方程：
# 2.1 dp[0]代表不偷该节点拿到最多的钱，则儿子节点偷不偷都ok。dp[0] = max(left[0], left[1]) + max(right[0], right[1])
# 2.2 dp[1]代表偷了该节点拿到最多的钱，则儿子节点都不能被偷。dp[1] = var + left[0] + right[0]
# 3.初始化：当前树的形状为空的时候，直接返回dp[0, 0]
def postTrasval(root):
dp = [0, 0]
if not root:
return dp
left = postTrasval(root.left)
right = postTrasval(root.right)
dp[0] = max(left[0], left[1]) + max(right[0], right[1])
dp[1] = root.val + left[0] + right[0]
return dp
dp = postTrasval(root)
return max(dp[0], dp[1])
if __name__ == '__main__':
# initial tree structure
T = TreeNode(3)
T.left = TreeNode(2)
T.right = TreeNode(3)
T.left.right = TreeNode(3)
T.right.right = TreeNode(1)
# The solution to the Question
s = Solution()
print(s.rob(T))
Пока все, что я хочу объяснить, закончилось.
Я написал 10 000 слов, и я не ожидал, что напишу так много
Позвольте мне подчеркнуть, что если вы понимаете все эти темы и дополнительно практикуетесь, вы сможете охватить их.На тему динамического программирования более 80%, в основном дп это одномерный массив, двумерный массив вопросов, появляется очень мало очень странных вопросов. Поэтому в этой статье подробно объясняется классический случай «Семейного ограбления», а также проблемы с разными путями, которые также являются очень классическими темами, а классические темы должны быть очень репрезентативными. Направлений оптимизации много, и в этой статье представлена только оптимизация пространства, потому что это самое распространенное.
В конце концов, каждый должен рисовать больше картинок, больше думать и решать проблемы для себя.
Кроме того, понять еще четыре шага, давай!
Позже у меня будет возможность подробно поделиться другими статьями об общих идеях алгоритмов.
Если вы чувствуете, что это полезно для всех, пожалуйста, подпишитесь, поставьте лайк и сделайте ретвит! ! !