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

Question

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

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

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

Answer 1

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