Контрпримеры, чтобы доказать, что запоминание в динамическом программировании не всегда полезно - PullRequest
0 голосов
/ 03 мая 2018

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

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

1 Ответ

0 голосов
/ 03 мая 2018

Нет! Запоминание не всегда полезно. Одним простым примером счетчика, о котором можно подумать, будет функция 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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...