很多算法问题可以通过深度优先搜索和动态规划两种算法来解决。这两种算法之间有直接或间接的联系吗?如果我想出了dp的子问题,如何将其转换为dfs中的递归函数?
深度优先搜索 + memoization(记忆化) = 动态规划
这个定义适用于许多问题。
根据动态规划的定义,它必须具有"最优子结构"。这意味着您可以使用子解决方案来获得通用解决方案。
换句话说,简单地说,您将使用f(n-1)之类的方法来表示f(n)。这个递归表达式可以直接使用深度优先搜索进行编码。
为了利用预先计算的子解或子结构,您使用memoization(记忆化)缓存子解决方案。这就是DP的全部内容。
P.S.:当然,您可以使用迭代循环方法来填充缓存,而不是DFS + memoization方法。但是,回答您的问题,这只会使其更难理解。
//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]
}