Рубрики

Табуляция против Мемоизации

Обязательное условие — динамическое программирование , как решить проблемы динамического программирования?
Существует два разных способа хранения значений, чтобы значения подзадачи можно было использовать повторно. Здесь будут обсуждаться две модели решения проблемы ДП:

    1. Табуляция: снизу вверх
    2. Мемоизация: сверху вниз

Прежде чем перейти к определениям двух приведенных выше терминов, рассмотрим следующие утверждения:

  • Версия 1 : Я буду изучать теорию динамического программирования от GeeksforGeeks, затем я буду практиковать некоторые проблемы на классическом DP и, следовательно, я буду осваивать динамическое программирование.
  • Версия 2 : Чтобы освоить динамическое программирование, мне нужно практиковаться в динамических задачах и практиковаться в проблемах. Во-первых, мне нужно изучить теорию динамического программирования в GeeksforGeeks.

Обе вышеприведенные версии говорят об одном и том же, различие заключается в способе передачи сообщения, и это именно то, что делают Bottom Up и Top Down DP. Версия 1 может быть связана с Bottom Up DP, а версия 2 — с Top Down Dp.

Метод табуляции — динамическое программирование снизу вверх

Поскольку само название предлагает начинать снизу и накапливать ответы сверху. Давайте обсудим с точки зрения перехода государства.

Давайте опишем состояние для нашей задачи DP: dp [x] с dp [0] в качестве базового состояния и dp [n] в качестве нашего конечного состояния. Итак, нам нужно найти значение состояния назначения, т.е. dp [n].
Если мы начинаем наш переход из нашего базового состояния, то есть dp [0], и следуем нашему отношению перехода между состояниями, чтобы достичь нашего конечного состояния dp [n], мы называем это подходом «снизу вверх», так как совершенно ясно, что мы начали наш переход с нижней базы состояние и достиг вершины самого желаемого состояния.

Теперь, почему мы называем это методом табуляции?

Чтобы узнать это, давайте сначала напишем некоторый код для вычисления факториала числа с использованием подхода снизу вверх. Еще раз, как наша общая процедура для решения DP, мы сначала определяем состояние. В этом случае мы определяем состояние как dp [x], где dp [x] — найти факториал x.

Теперь совершенно очевидно, что dp [x + 1] = dp [x] * (x + 1)

// Tabulated version to find factorial x.
int dp[MAXN];

// base case
int dp[0] = 1;
for (int i = 1; i< =n; i++)
{
    dp[i] = dp[i-1] * i;
}

Приведенный выше код явно следует восходящему подходу, поскольку он начинает свой переход с самого нижнего базового случая dp [0] и достигает состояния назначения dp [n]. Здесь мы можем заметить, что таблица dp заполняется последовательно, и мы напрямую обращаемся к вычисленным состояниям из самой таблицы, и, следовательно, мы называем это методом табуляции.

Метод мемоизации — динамическое программирование сверху вниз

Еще раз, давайте опишем это с точки зрения перехода состояния. Если нам нужно найти значение для некоторого состояния, скажем, dp [n], и вместо того, чтобы начинать с базового состояния, то есть dp [0], мы запрашиваем наш ответ из состояний, которые могут достичь состояния назначения dp [n] после перехода состояния отношение, то это мода сверху вниз DP.

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

Еще раз, давайте напишем код для факториальной проблемы сверху вниз

// Memoized version to find factorial x.
// To speed up we store the values
// of calculated states

// initialized to -1
int dp[MAXN]

// return fact x!
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

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

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

Эта статья предоставлена Нитишем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью, используя или отправив свою статью по адресу contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Табуляция против Мемоизации

0.00 (0%) 0 votes