algorithm - 回溯与动态规划的区别

Question

我听说动态规划和回溯之间的唯一区别是 DP 允许重叠子问题，例如

fib(n) = fib(n-1) + fib (n-2)

是吗？还有其他区别吗？

另外，我想知道使用这些技术解决的一些常见问题。

Answer 1

动态规划方法有两种典型的实现方式:自下而上和自上而下。

自上而下的动态规划只不过是普通的递归，通过内存中间子问题的解决方案得到增强。当给定的子问题出现第二次(第三次、第四次……)时，它不会从头开始解决，而是立即使用先前内存的解决方案。这种技术以名称​​内存(“i”前没有“r”)而为人所知。

这实际上就是您使用斐波那契数列的示例应该说明的内容。只需使用 Fibonacci 数列的递归公式，但沿途构建 fib(i) 值表，您将获得针对此问题的自上而下的 DP 算法(这样，例如, 如果你需要第二次计算 fib(5) ，你可以从表中获取它而不是再次计算它)。

在自下而上的动态规划中，该方法也基于将子解存储在内存中，但它们以不同的顺序求解(从小到大)，并且生成的一般算法的结构不是递归的。 LCS algorithm是一个经典的 Bottom-to-top DP 示例。

自下而上的 DP 算法通常更有效，但它们通常更难(有时甚至不可能)构建，因为预测您将需要解决整个问题的原始子问题并不总是那么容易原始问题，以及您必须从小的子问题中采取哪条路径才能以最有效的方式获得最终解决方案。