«Алгоритмы и структуры данных» Карта мозга показывает красоту алгоритмов динамического программирования.

внешний интерфейс алгоритм
«Алгоритмы и структуры данных» Карта мозга показывает красоту алгоритмов динамического программирования.

предисловие

В алгоритме есть тема, динамическое программирование, очень важная, она более-менее задействована в интервью большой фабрики.NetEaseРаньше я расчесывала немного dp, на этот раз просто расчесала еще раз, надеюсь, это вам немного поможет.

Если вы уже понимаете идею dp или освоили общее решение dp, вы можете сразу его пропустить.

Если вы еще этого не знаете, или знаете о динамическом программировании, но еще не начали причесываться к теме, возможно, эта статья для вас.

Нет публикиИнтерфейс UpUp, ответьте дп, вы можете получить карту мозга.

Свяжитесь с 👉TianTianUp, если у вас возникнут проблемы, вы можете связаться с автором, я готов сопровождать вас, чтобы вместе изучить и обсудить проблему.

Карта мозга👇

Что такое динамическое программирование

Динамическое программирование (Dynamic Programming), поэтому DP часто используется для обозначения динамического программирования. Динамическое программирование, прежде всего, мы должны четко понимать, в чем его концепция, какие проблемы оно может решить, Википедия объясняет это 👇

Динамическое программирование эффективно при поиске оптимальных решений для ситуаций с множеством перекрывающихся подзадач. Он перегруппирует проблему в подзадачи, и, чтобы избежать многократного решения этих подзадач, их результаты постепенно вычисляются и сохраняются, от простых проблем до решения всей проблемы. Поэтому динамическое программирование сохраняет результаты рекурсии, поэтому на решение одной и той же задачи не уходит время.

Динамическое программирование применимо только к задачам с оптимальной структурой. Оптимальная подструктура означает, что локальное оптимальное решение может определять глобальное оптимальное решение (для некоторых задач это требование не может быть полностью удовлетворено, поэтому необходимо вводить некоторые приближения). Проще говоря, проблему можно решить, разбив ее на подзадачи.

Немного подытожу 👇

  • Разделите большую проблему на подзадачи, которые мы называем подструктурами.
  • Каждое оптимальное решение, т.Оптимальное значениеявляются производными от [этих мелких подзадач].
  • Что еще более важно, используйте历史记录, чтобы избежать повторных вычислений.

Что такое двойной расчет, как мы можем использовать исторические записи, чтобы уменьшить наши ненужные операции👇

мы принимаемПоследовательность ФибоначчиПосмотрите на этот вопрос 👇

Если мы будем следовать этому рекурсивному способу записи, то его процесс будет следующим👇

Он вычисляет результат несколько раз, и это соответствует смыслу динамического программирования. **Динамическое программирование эффективно при поиске наилучшего решения для ситуаций со многими перекрывающимися подзадачами. ** И для этой проблемы ее можно по-прежнему разбивать на более мелкие подзадачи для решения, что также соответствует ожиданиям динамического программирования.

Так вот это просто пример, а следующим вопросом будет идея👇

Три шага динамического программирования

Для новичков, если освоить недолго, думаю очень сложно, так что тут всем рекомендую глянутьКлассическое динамическое программирование👉Девять лекций о рюкзаках,кликните сюда, после прочтения, возможно, это вам немного поможет.

Идеи решения проблем, три шага 👇

  1. определение состояния
  2. Список уравнений перехода состояния
  3. инициализированное состояние

определение состояния

  • Нам нужно использовать массивы для сохранения результатов предыдущих вычислений, поэтому мы обычно используем массивы для сохранения наших результатов, как правило, массивы dp.
  • Смысл массива dp должен быть ясен, то есть что означает dp[i], например, dp[i] выражает количество решений при достижении i-й лестницы.

Список уравнений перехода состояния

  • Легко понять, то, чтобы выяснить отношения между массивом, чтобы решить проблему динамической спецификации, самый сложный и самый важный шаг в это время.
  • В общем, уравнения перехода состояний dp[i] имеют некоторую связь с dp[i-1] и dp[i-2].

Например, после爬梯子В названии , уравнение перехода состояния 👇

dp[i] = dp[i-1] + dp[i-2]
  • Во-первых, dp[i] представляет количество решений i-го шага.
  • Тогда поднимитесь на i-ю ступеньку, есть две ситуации👇
    • Поднимитесь еще на одну ступеньку с i-1 ступеньки на i-ю ступеньку
    • Ползание 2-го порядка с первой фазы I-2 шагов
  • Тогда его переход уравнения состояния представляет собой приведенную выше формулу

инициализированное состояние

  • Мы обнаружим, что результат n-го элемента массива dp соответствует решению уравнения перехода состояния, поэтому нам нужно значение n-1-го элемента, n-2 элемента или n-3 элемента. .
  • На данный момент нам нужно значение начального массива dp, вообще говоря, такое какdp[1],dp[2],dp[1][1],dp[1][2].

Из приведенной выше сцены, с точки зрения подъема по лестнице, какой массив dp нам нужен изначально?Когда мы перейдем к dp[3] = dp[1] + dp[2], нам больше не нужно разлагать .

На данный момент, в нашем практическом смысле, нам нужно инициализировать массивы dp[1] и dp[2].

классификация динамического программирования

С тех пор, как идея алгоритма динамического программирования исследовалась многими экспертами, такие проблемы, как динамическое программирование, были разделены на множество видов.Ссылаясь на информацию в Интернете, перечислены несколько распространенных DP.Давайте возьмем Смотреть.

По моему опыту браширования по разным темам дп, эффект налицо, конечно, зависит от собственного понимания ситуации и скорости браширования вопросов.

рюкзак дп

Это относительно классическая тема в государственном планировании, лично для меня она очень полезна для понимания дп, а также это первая тема, которую я читаю, когда начинаю дп👇

"Девять лекций о рюкзаке" д. д. Даниэля👈, вы можете ознакомиться с этой статьей, здесь она не будет расширяться.

Вот несколько рекомендуемых вопросов 👇

линейное дп

  • Как следует из названия, линейный DP — это DP на линии.
  • Или я понимаю, что это рекурсия в линейном пространстве.

Вот несколько рекомендуемых вопросов 👇

интервал дп

  • Как следует из названия, dp за интервал, аналогичныйdp[l][r]Мы также разделяем большие проблемы на маленькие проблемы, с которыми нужно иметь дело, здесь мы разбиваем их на небольшие разделы, с которыми приходится иметь дело.

  • Затем, после обработки малого интервала, значение большого интервала получается ретроспективно.

  • Есть два основных метода: мемоизированный поиск и рекурсия.

Вот несколько рекомендуемых вопросов 👇

дерево ДП

  • Если быть точным, tree dp — это именно своего рода идея dp, которая строит dp на основе древовидной структуры.
  • Вы можете понимать это как определение уравнения dp на дереве и выполнение соответствующих операций.

Вот несколько рекомендуемых вопросов 👇

цифровое двойное проникновение

  • Цифровой dp — это тип dp, используемый для подсчета, который обычно используется для подсчета количества чисел, удовлетворяющих некоторым условиям в интервале [le, ri].
  • Так называемое цифровое дп буквально означает выполнение дп на цифре.
  • Цифры - очень красивое название.Значение цифр: число имеет цифру, разряд десятков, разряд сотен, разряд тысяч... Каждая цифра числа - цифра!

Вот несколько рекомендуемых вопросов 👇

На мой взгляд, это шаблон, и написать его самому сложно, но это вопрос доски, хахаха, я знаю, что играл в Acm, поэтому не буду здесь его разворачивать.

Государственное сжатие DP Подсчет ДП Рекурсивный ДП Вероятностный ДП игровое двойное проникновениехм, слишком много, просто возьмите это как руководство.

3 примера

Далее, давайте возьмем три вопроса в качестве примера, чтобы усилить три шага наших идей по решению проблем👇

Восхождение по лестнице⭐

Связь:подниматься по лестнице

Предположим, вы поднимаетесь по лестнице. нужноnшаги, чтобы достичь вершины.

Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания?

**ПРИМЕЧАНИЕ: **Даноnявляется положительным целым числом.

Пример 1:

  1. 输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶

    Пример 2:

  2. 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Источник: LeetCode Связь:Lee TCO's-talent.com/problems/besides…Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

Давайте рассмотрим идею решения проблемы 👇

Шаг 1: определение состояния

Значение dp[i]: количество решений i-го порядка

Шаг 2: Определите уравнение перехода состояния

В соответствии с реальной ситуацией, мы можем легко придумать👇

  • Есть два способа добраться до i-го шага
  • Первый, просто сделайте один шаг вверх от i-1
  • Во втором сделайте два шага вверх от i-2
  • Итак, dp[i] = dp[i-1] + dp[i-2]

Третий шаг, инициализация состояния, массив dp

dp[1] = 1,dp[2] = 2

Если мы выполним эти три шага, мы сможем написать полный код для решения проблем.

код👇

Код нажмите здесь ☑️

ограбление 🐍⭐⭐

Связь:Расхитители дома 2

Вы профессиональный вор, планирующий украсть дома вдоль улицы, в каждом из которых спрятана определенная сумма денег. Все дома в этом месте расположены по кругу, что означает, что первый дом и последний дом находятся рядом друг с другом. В то же время соседние дома оборудованы взаимосвязанными противоугонными системами: если воры взломают два соседних дома в одну и ту же ночь, система автоматически подаст сигнал тревоги.

Учитывая массив неотрицательных целых чисел, представляющих сумму, хранящуюся в каждом доме, рассчитайте максимальную сумму, которую вы можете украсть, не активировав тревогу.

Пример 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

Пример 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

Источник: LeetCode Связь:Lee TCO's-talent.com/problems/ хорошо…Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

Давайте рассмотрим идею решения проблемы 👇

Шаг 1: определение состояния

// 这里就利用二维状态,既然可以选择偷或者是不偷

// dp[i][0] 表示不偷当前第i个房间,获取最高金币数

// dp[i][1] 表示的是偷第i房间,获取最高金币数

Шаг 2: Определите уравнение перехода состояния

// 第i个房间偷的话,dp[i][1] = nums[i] + dp[i-1][0]
// 第i个房间不偷的话, dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])

Третий шаг, инициализация состояния, массив dp

// dp[0][0] = 0
// dp[0][1] = nums[0]

Но сложность этой темы в том, что 👇

Первый дом и последний дом стоят рядом, а это значит, что нам нужно внести некоторые изменения. Это я тоже выполнил под подсказкой. Способ написания очень хитрый. Давайте посмотрим на код ниже👇

Если мы выполним эти три шага, мы сможем написать полный код для решения проблем👇

Код нажмите здесь ☑️

Лучшее время для покупки и продажи акций IV⭐⭐⭐

Дайте вам бинарное дерево, пожалуйста, верните егообход по уровнямПолученное значение узла. (т.е. слой за слоем, посещая все узлы слева направо).

Связь:Лучшее время для покупки и продажи акций IV

Дан массив, i-й элемент которого — цена данной акции в i-й день.

Разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Вы можете совершить до k транзакций.

Примечание. Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущие акции, прежде чем покупать снова).

Пример 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

Пример 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

Источник: LeetCode Связь:Lee TCO's-talent.com/problems/не голоден…Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

Шаг 1: определение состояния

 // 可以定义如下
 // dp[i][j][0] 表示第i天交易了j次时卖出后的累计最大利润
 //  dp[i][j][1] 表示第i天交易了j次时买入后的累计最大利润

Шаг 2: Определите уравнение перехода состояния

  // 第二步：确定状态转移方程
 // dp[i][j][0] 当第i天不持股的话，我们需要确定昨天是否持有股票
 // dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
 // dp[i][j][1] 同样的第i天,我们需要去确定昨天是否持有股票
 // dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])

Третий шаг, инициализация состояния, массив dp

// 所有不持股的状态值初始化的时候为 0。所有持股的状态值都设置为一个很大的负数（至少应该是最大的股价的负数 - 1），表示未知。
// dp[0][j][0] = 0;
// dp[0][j][1] = -prices[i];

Но сложность этой темы в том, что 👇

Когда k больше, чем len/2, нам нужно сделать процесс, или нам нужно использовать сжатие состояния, это очень сложно, давайте посмотрим, как это написать👇

Код нажмите здесь ☑️

Краткое изложение дополнительных тем

Ниже приведены некоторые из тем, которые я собрал, я надеюсь помочь вам.

Простой

Средняя

трудность

Ссылаться на

❤️ Всем спасибо

Если вы считаете этот контент полезным:

  1. Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
  2. Обратите внимание на публичный аккаунтИнтерфейс UpUp, свяжитесь с автором, мы будем учиться и прогрессировать вместе.
  3. Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):
Категории