Контрпримеры, чтобы доказать, что запоминание в динамическом программировании не всегда полезно

Question

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

Пожалуйста, поправьте меня, если я что-то ошибаюсь.

Answer 1

Нет! Запоминание не всегда полезно. Одним простым примером счетчика, о котором можно подумать, будет функция factorial(n), в которой вам нужно вычислить факториал для данного числа n.

factorial(n): if(n = 1) return; else return n*factorial(n-1);
Рассмотрим приведенный выше псевдокод для вычисления факториала с заданным числом n. Скажем, n = 5, функция будет вычислять factorial(5) так:

• 5 *factorial(4)
• 4 *factorial(3)
• 3 *factorial(2)
• 2 *factorial(1)
• 1 *factorial(0)
• 1

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

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