如何在DFS和DP中解决算法问题

Question

很多算法问题可以通过深度优先搜索和动态规划两种算法来解决。这两种算法之间有直接或间接的联系吗？如果我想出了dp的子问题，如何将其转换为dfs中的递归函数？

- Hongli Bu

---

也许这个问题太笼统了，但我真的很困惑为什么这两种算法都可以解决许多问题？ - Hongli Bu

Answer 1

深度优先搜索 + memoization（记忆化） = 动态规划

这个定义适用于许多问题。

根据动态规划的定义，它必须具有"最优子结构"。这意味着您可以使用子解决方案来获得通用解决方案。

换句话说，简单地说，您将使用f（n-1）之类的方法来表示f（n）。这个递归表达式可以直接使用深度优先搜索进行编码。

为了利用预先计算的子解或子结构，您使用memoization（记忆化）缓存子解决方案。这就是DP的全部内容。

P.S.：当然，您可以使用迭代循环方法来填充缓存，而不是DFS + memoization方法。但是，回答您的问题，这只会使其更难理解。

- CodingLab

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]
}

- DemiDust