Как решить проблемы алгоритма в DFS и DP

Question

Многие проблемы алгоритма могут быть решены с помощью DFS и динамического программирования.Есть ли прямые или косвенные связи между этими двумя алгоритмами?Или, если я придумал подзадачу dp, как я могу преобразовать ее в рекурсивную функцию в dfs?

Answer 1

dfs + memoization = dp

во многих задачах.

по определению dp должен иметь "оптимальную подструктуру".

это означает, что вы можете использовать вспомогательное решение для получения обобщенного решения.

другими словами, просто сказав, что вы выразите f (n), используя f (n-1) или около того.

и это рекурсивное выражение может быть непосредственно закодировано с использованием dfs.

и для того, чтобы воспользоваться преимуществами предварительно рассчитанного под-решения или подструктуры, вы кешируете под-решение, используя памятку.

и это все, что представляет собой dp.

ps, конечно, вы можете использовать метод итеративного цикла для заполнения кэша вместо подхода dfs + памятка.но ответить на ваш вопрос может только затруднить понимание.

Answer 2

Динамическое программирование - это один из способов повысить эффективность алгоритма, сохранив его в памяти, или, скажем, запоминание.Его можно комбинировать с любым типом алгоритма, это особенно полезно для алгоритма перебора в примере dfs.

Одним из простых примеров является Фибоначчи.Я предполагаю, что вы уже знаете, как решать фибоначчи с помощью рекурсии (dfs).

С помощью dp вам больше не нужно вычислять одно и то же значение, поскольку вы будете хранить значение (обычно в массиве).

Пример псевдокода:

//each arr default value will be 0
declare fibArr size n
fibArr[0] = 1
fibArr[1] = 1

function fib(int number)
{
     //return the fibonacci number if it has been calculated beforehand
     if(fibArr[number] != 0)
         return fibArr[number]

     fibArr[number] = fib(number-1) + fib(number-2)
     return fibArr[number]
}