На самом деле динамическое программирование - это человеческое мышление. Если у вас есть один вопрос, на который вы можете разделить его на несколько подвопросов, на которые у вас уже есть ответы, вам не нужно снова пытаться решить те же проблемы.
Подумайте, вам нужно найти рынок по городу. Вы прошли несколько маршрутов, спросили у местных жителей и через некоторое время оказались на рынке. На следующий день вы хотели купить лекарства, и люди говорили, что рядом с рынком есть аптека. Итак, на данный момент у вас есть действительно четкое представление о местонахождении аптеки.
Так как же это случилось? Потому что вы разделили проблему на две подзадачи.
- Где рынок?
- Где находится аптека?
У вас есть ответ на первый вопрос, вы уже ответили на этот вопрос, вчера решили этот вопрос. Так что вам не нужно решать это, вам просто нужно снова пойти на рынок и найти рядом с ним аптеку. И тогда это станет вашим окончательным ответом. Это все о «динамическом программировании».
Вот еще один математический пример. Это один из наиболее распространенных примеров динамического программирования, поэтому я собираюсь использовать его, проблема Фибоначчи. Фибоначчи можно объяснить следующим образом:
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). Это называется мемоизацией. Мы производим вычисления, когда нам это нужно, и сохраняем их в массиве, чтобы запомнить. Каждый раз, когда нам нужно значение, сначала мы проверяем наш массив, если мы не вычислили это значение, мы выполним свою работу.
С другой стороны, табуляция - это восходящий метод. Сначала мы вычислим все значения, поместим их в массив. И наш окончательный расчет будет сделан с использованием этого массива.
Когда вы сравниваете табуляцию и мемоизацию, оба они могут использоваться в целом, но у них также есть свои плюсы и минусы. Мемоизацию можно считать более эффективной, но когда нам нужно найти результаты множества операций, это означает, что множество рекурсивных операций может привести к сбою операции.
Поскольку табуляция заполняет наш массив вначале, а затем вычисляет результат сразу, табуляция может решить нашу проблему. Но помните, что у вас ограниченная память!
Так что это зависит от обстоятельств! Вы можете использовать оба метода, чтобы сделать вашу работу более эффективной. Алгоритмы лучше, когда их запоминают!
Когда я познакомился с динамическим программированием, это был отличный момент, чтобы понять, насколько это базовое и насколько эффективно. Я предлагаю вам написать свои собственные методы и попробовать посмотреть, как они делают вашу задачу проще и эффективнее. Когда ты тренируешься, всегда лучше! Спасибо за уделенное время и надеюсь увидеть вас в моем следующем рассказе!