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

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

Соответствующая статья о Программировании. Гид: Динамическое программирование против запоминания против табуляции

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

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

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

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

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

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

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

Хороший слайд отсюда (ссылка сейчас мертва, слайд все еще хорош):

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

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

• Википедия: Мемоизация , Динамическое программирование
• Связанные SO Q / A: подход Memoization или Tabulation для динамического программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

мемоизации

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

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

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

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

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

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

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

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

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

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

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

Проблема:

Вы поднимаетесь по лестнице. Требуется 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/

Просто подумай о двух способах,

1. Мы разбиваем большую проблему на меньшие подзадачи - подход сверху вниз.
2. Мы начинаем с самой маленькой подзадачи и достигаем большей проблемы - подхода «снизу вверх».

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

В динамическом программировании мы используем (2.), где поддерживаем таблицу снизу вверх, решая подзадачи с использованием данных, сохраненных в таблице, обычно называемой dp-таблицей.

Примечание:

• И то и другое применимо к проблемам с перекрывающимися подзадачами.

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

• Асимптотическая временная сложность остается прежней.

В динамическом программировании ,

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

В запоминании ,

• Некоторые подзадачи не должны быть решены.