memoization vs сложность динамического программирования

Question

Я хочу знать, что проблема связана с LCS, мы можем уменьшить сложность пространства для решения dp, потому что когда мы заполняем таблицу в dp, мы просто используем либо dp[i - 1][j], либо dp[i][j - 1], чтобы заполнить dp[i][j], а вместо имеющий таблицу dp размера m X n.

Мы можем решить это, используя dp[2][n] и состояния состояний переключателя при расчете. Возможно ли это с помощью запоминания для уменьшения сложности пространства до O (n + m)?

Answer 1

Простого ответ NO

В нижней части вверх можно удалить строки, которые не являются необходимыми только потому, что вы знаете, эти строки не будут использоваться снова .... В запоминании, рекурсия вызовы в любом а не полный формальный метод, например: есть вызов от LCS (i, j) к LCS (i-1, j), и пусть этот результат будет вычислен и сохранен! Теперь Recursion вызывает LCS (k, x) (для некоторого другого случая), который приводит к одной и той же подзадаче LCS (i-1, j) И теперь, если вы удалили это сохраненное значение, которое не будет правильно запоминать решение ...!

Вы не можете быть уверены в том, какая подзадача Memoize и не memoize. В отличие от снизу вверх Мы уверены, что подзадачи не будут использоваться снова (Thats, почему мы устраняем другие строки)!