Динамическое программирование - сверху вниз и снизу вверх

Question

Я узнал, что динамическое программирование (ДП) бывает двух видов: сверху вниз и снизу вверх.

В нисходящем порядке вы используете рекурсию вместе с напоминанием. В восходящем направлении вы просто заполняете массив (таблицу).

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

Answer 1

Ну, я считаю, что теоретически вы должны быть в состоянии решить проблему DP с любым подходом. Однако есть случаи, когда подход снизу вверх может стать слишком дорогим. Рассмотрим проблему ранца с knapsack_size = 200,000 и num_items = 2000, Чтобы заполнить двумерную таблицу DP просто ints не будет возможно. Вы исчерпаете основную память обычного компьютера. Более того, вам не требуется заполнять все записи в таблице для достижения желаемого окончательного расчета. В таком случае рекурсивный нисходящий подход намного лучше. Надеюсь, поможет.

Answer 2

При решении динамической задачи вы можете учитывать две вещи...

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

       if all sub-problems need not to be solved
    top-down
else
    bottom-up

2. Существует преимущество в восходящем порядке с точки зрения требований к пространству. Потому что это экономит много места в стеке по сравнению с рекурсивным нисходящим подходом. Таким образом, для оптимального пространства

       bottom-up

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

Answer 3

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

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

PS: чтобы увидеть разницу между временными сложностями сверху вниз и снизу вверх, вам нужно решить задачу ASSIGNMENTS на SPOJ.