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

Подумайте, вам нужно найти рынок по городу. Вы прошли несколько маршрутов, спросили у местных жителей и через некоторое время оказались на рынке. На следующий день вы хотели купить лекарства, и люди говорили, что рядом с рынком есть аптека. Итак, на данный момент у вас есть действительно четкое представление о местонахождении аптеки.

Так как же это случилось? Потому что вы разделили проблему на две подзадачи.
- Где рынок?
- Где находится аптека?
У вас есть ответ на первый вопрос, вы уже ответили на этот вопрос, вчера решили этот вопрос. Так что вам не нужно решать это, вам просто нужно снова пойти на рынок и найти рядом с ним аптеку. И тогда это станет вашим окончательным ответом. Это все о «динамическом программировании».

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

F (0) = F (1) = 1 и F (n) = F (n-1) + F (n-2), для n ›1

Итак, если вы хотите найти F (n), сначала вам нужно решить два вопроса: F (n-1) и F (n-2). Некоторые примеры;

F(2) = F(1)+F(0)

F(3) = F(2) + F(1) = (F(1)+F(0)) + F(1)

F(4) = F(3) + F(2) = (F(2)+F(1)) + (F(1)+F(0))
F(4)= ((F(1)+F(0)) + F(1)) + (F(1) + F(0))

Если вы хотите найти F (3), вам нужно найти F (2) и F (1), после этого, если вы хотите найти F (4), вам нужны F (3) и F (2), но вы уже имеют их ценности. Их не нужно пересчитывать!

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

Динамическое программирование может быть выполнено двумя способами: «Запоминание» и «Табулирование».

Мемоизация - это нисходящий подход.

Когда мы смотрим на это изображение, которое представляет собой график F (5), чтобы найти F (5), соответственно нам нужно найти F (4), F (3), F (2), F (1), F (0).

Сразу после прохождения по этому маршруту решится и отдых. Таким образом, мы
не будем пересчитывать одни и те же значения, а это значит, что мы сохраним в общей сложности 9 вычислений для F (5). Это называется мемоизацией. Мы производим вычисления, когда нам это нужно, и сохраняем их в массиве, чтобы запомнить. Каждый раз, когда нам нужно значение, сначала мы проверяем наш массив, если мы не вычислили это значение, мы выполним свою работу.

С другой стороны, табуляция - это восходящий метод. Сначала мы вычислим все значения, поместим их в массив. И наш окончательный расчет будет сделан с использованием этого массива.

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

Поскольку табуляция заполняет наш массив вначале, а затем вычисляет результат сразу, табуляция может решить нашу проблему. Но помните, что у вас ограниченная память!

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

Когда я познакомился с динамическим программированием, это был отличный момент, чтобы понять, насколько это базовое и насколько эффективно. Я предлагаю вам написать свои собственные методы и попробовать посмотреть, как они делают вашу задачу проще и эффективнее. Когда ты тренируешься, всегда лучше! Спасибо за уделенное время и надеюсь увидеть вас в моем следующем рассказе!