В чем разница между запоминанием и динамическим программированием?

Question

В чем разница между запоминанием и динамическим программированием?Я думаю, что динамическое программирование - это подмножество воспоминаний.Это правильно?

Answer 1

В чем разница между запоминанием и динамическим программированием?

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

Динамическое программирование - это методика решения задач рекурсивного характера, итеративная, и она применима, когда вычисления подзадач перекрываются.

Динамическое программирование обычно реализовано с использованием табуляции, но также может быть реализовано с использованием мемоизации. Итак, как вы можете видеть, ни один из них не является «подмножеством» другого.

---

Разумный дополнительный вопрос: В чем разница между табулированием (типичная техника динамического программирования) и запоминанием?

Когда вы решаете задачу динамического программирования с использованием табуляции, вы решаете проблему " снизу вверх ", т. Е. Сначала решая все связанные подзадачи, обычно заполняя n стол. На основании результатов, приведенных в таблице, затем вычисляется решение "верхней" / исходной проблемы.

Если вы используете памятку для решения проблемы, вы делаете это, поддерживая карту уже решенных подзадач. Вы делаете это " сверху вниз " в том смысле, что сначала вы решаете "верхнюю" проблему (которая обычно повторяется вниз для решения подзадач).

Хороший слайд из здесь (ссылка сейчас не работает, хотя слайд еще хорош):

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

Дополнительные ресурсы:

• Википедия: Заметки , Динамическое программирование
• Связанные SO Q / A: Подход с учетом или табулированием для динамического программирования

---

Это было переписано как статья здесь .

Answer 2

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

http://www.geeksforgeeks.org/dynamic-programming-set-1/

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

См. в этом обсуждении по запоминанию против табуляции.

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

Answer 3

Динамическое программирование часто называют Memoization!

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

2. DP находит решение, начиная с базового (-ых) случая (-ов), и направляется вверх.DP решает все подзадачи, потому что он делает это снизу вверх

   В отличие от Memoization, который решает только необходимые подзадачи

3. У DP есть потенциал, чтобы преобразовать экспоненциальные решения грубой силы в алгоритмы за полиномиальное время.

4. DP может быть намного более эффективным, потому что его итеративное

   OnНапротив, Memoization должен оплачивать (часто существенные) накладные расходы из-за рекурсии.

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

Answer 4

(1) Memoization и DP, концептуально , на самом деле одно и то же. Потому что: рассмотрим определение ДП: «перекрывающиеся подзадачи» и «оптимальная подструктура». Мемоизация полностью обладает этими 2.

(2) Memoization - это DP с риском переполнения стека в случае глубокой рекурсии. У DP снизу вверх нет этого риска.

(3) Для запоминания нужна хеш-таблица. Таким образом, дополнительное пространство и некоторое время поиска.

Итак, чтобы ответить на вопрос:

- Концептуально , (1) означает, что это одно и то же.

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

- Принимая во внимание (3), они имеют незначительные различия в производительности.

Answer 5

Из википедии:

Запоминание

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

Динамическое программирование

В математике и информатике динамическое программирование - это метод решения сложных задачразбивая их на более простые подзадачи.

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

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

Answer 6

И Мемоизация, и Динамическое программирование решают отдельные подзадачи только один раз.

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

Ниже приведена интересная аналогия -

Сверху вниз - Сначала вы скажете, что я завоюю мир.Как ты это сделаешь?Вы говорите, что сначала я захватлю Азию.Как ты это сделаешь?Я сначала возьму на себя Индию.Я стану главным министром Дели и т. Д. И т. Д.

Вверх - Вы говорите, что я стану СМ Дели.Затем возьму на себя Индию, затем все другие страны Азии и, наконец, я возьму на себя весь мир.

Answer 7

Я бы хотел привести пример ;

Проблема:

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

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

Рекурсия с памяткой

Таким образом мы обрезаем (удаляем лишний материал из дерева или куста) дерево рекурсии с помощью массива memo и уменьшаем размер дерева рекурсии до nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Динамическое программирование

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

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Примеры взяты из https://leetcode.com/problems/climbing-stairs/