如何解决dfs和dp中的算法问题

Question

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

Answer 1

dfs + 记忆化 = dp

在许多问题中。

根据定义 dp 必须具有“最佳子结构”。

这意味着您可以使用子解决方案来获得通用解决方案。

换句话说，简单地说你将使用 f(n-1) 左右表达 f(n)。

这个递归表达式可以直接使用 dfs 编码。

并且为了利用预先计算的子解决方案或子结构，您可以使用记忆化来缓存子解决方案。

这就是 dp 的全部内容。

ps当然你可以使用迭代循环方法来填充缓存而不是dfs+memoization方法。但要回答你的问题，这只会让人难以理解。

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