许多算法问题都可以通过 DFS 和动态规划来解决。这两种算法之间有直接或间接的联系吗？或者如果我想到了 dp 的子问题，我怎样才能将其转换为 dfs 中的递归函数？
最佳答案
DFS + memoization = DP
作为一个定义适用于许多问题。
根据动态规划的定义，它必须有 "optimal substructure" .这意味着您可以使用子解决方案来获得通用解决方案。
换句话说，简单地说您将使用 f(n-1) 左右来表达 f(n)。这个递归表达式可以使用深度优先搜索直接编码。
为了利用预先计算的子解决方案或子结构，您可以使用 memoization 缓存子解决方案。这就是DP的全部。
P.S.:当然你可以使用迭代循环的方法来填充缓存，而不是 DFS + memoization 的方法。但是要回答你的问题，这只会让它更难理解。
关于dynamic-programming - 如何解决 dfs 和 dp 中的算法问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54016101/