回溯和动态编程之间的区别

回溯和动态编程之间的区别

动态编程方法有两种典型的实现方式：从 底部到顶部 和从 顶部到底部 。

从上到下的动态编程 无非是普通的 递归
，它通过记忆中间子问题的解决方案而得到增强。当给定的子问题第二次（第三，第四…）出现时，它不是从头开始解决的，而是立即使用先前记忆的解决方案。这项技术被称为
备忘录 （在“ i”之前没有“ r”）。

这实际上就是您的斐波那契数列示例所要说明的内容。只需对Fibonacci序列使用递归公式，但

fib(i)

沿此过程构建值表，就可以针对此问题获得自上而下的DP算法（例如，如果需要

fib(5)

第二次计算，则得到而不是从表格中重新计算）。

在 自下而上的动态编程中，
该方法还基于将子解决方案存储在内存中，但是它们以不同的顺序（从小到大）求解，并且该算法的结果一般结构不是递归的。LCS算法是经典的从下到上的DP示例。

自下而上的DP算法通常效率更高，但是通常很难构建（有时甚至不可能），因为预测要解决整个原始问题所需的原始子问题并不总是那么容易，以及您必须从小子问题中走出的路径，以最有效的方式到达最终解决方案。