Как работает метод динамического программирования сверху вниз и снизу вверх?

Метод динамического программирования сверху вниз (Top-Down) работает так: начинается с решения основной задачи, которая постепенно разбивается на более мелкие подзадачи. 1 Затем каждая подзадача решается рекурсивно, при этом используется мемоизация (запоминание результатов решения подзадач) для избегания повторных вычислений. 2 В конце объединяются результаты решённых подзадач для получения решения основной задачи. 1

Метод динамического программирования снизу вверх (Bottom-Up) работает так: начинается с решения наименьших подзадач и постепенно комбинирует их результаты для решения более крупной задачи. 2 Этот метод избегает рекурсии и обычно использует циклы для эффективной обработки задачи. 2 Вычисления производятся с самой маленькой подзадачи, решение которой сохраняется в массиве. 2 Для решения более крупных подзадач используются решения более мелких подзадач. 2