我听说动态规划和回溯的唯一区别在于DP允许子问题重叠,例如:
fib(n) = fib(n-1) + fib (n-2)
这样做正确吗?还有其他的区别吗?
另外,我想知道使用这些技术解决了哪些常见问题。
我听说动态规划和回溯的唯一区别在于DP允许子问题重叠,例如:
fib(n) = fib(n-1) + fib (n-2)
这样做正确吗?还有其他的区别吗?
另外,我想知道使用这些技术解决了哪些常见问题。
fib(i)
值的表格,就可以得到该问题的自顶向下DP算法(例如,如果需要第二次计算fib(5)
,则可以直接从表格中获取其值而无需再次计算)。另一个区别可能是动态编程问题通常依赖于最优原则。最优原则指出,在一系列的决策或选择中,每个子序列都必须是最优的。
回溯问题通常在其过程中不是最优的!它们只适用于允许部分候选解概念的问题。
简单来说,动态规划是解决优化问题的一种策略。优化问题是指求最小值或最大值(一个结果)。但是,在回溯法中,我们使用暴力方法,不是为了解决优化问题,而是当你有多个结果时,你想要全部或部分结果。
原始答案翻译成中文是最初的回答。
利用边界函数生成状态空间树的深度优先节点生成被称为回溯。在这里,当前节点依赖于生成它的节点。
利用记忆函数生成状态空间树的深度优先节点生成被称为自顶向下动态规划。在这里,当前节点依赖于它所生成的节点。