了解动态规划

动态程序设计是一种解决复杂问题的方法，它将问题划分为更小的子问题，并为这些子问题寻找解决方案。我们将子问题的解决方案累积起来，从而找到全局解决方案。动态程序设计的好处在于，我们可以通过存储子问题的结果来减少对子问题的重新计算。动态编程是一种非常著名的优化方法。在程序设计领域，动态算法的应用随处可见。

动态编程可以解决诸如硬币变化、寻找最长公共子序列、寻找最长递增序列、DNA 字符串测序等问题。贪心算法与动态编程的核心区别在于，动态编程总是倾向于全局优化的解决方案。

如果问题具有最优子结构或重叠子问题，我们就可以用动态编程来解决问题。最优子结构指的是，实际问题的优化可以通过组合子问题的最优解来解决。换句话说，如果一个问题针对 n 进行了优化，那么它将针对小于 n 或大于 n 的任何大小进行优化。斐波那契数列就是重叠子问题的一个很好的例子。因此，在这里使用基本递归完全无济于事。动态程序设计对每个子问题都只解决一次，而不会进一步解决。它可以通过自上而下或自下而上的方法实现。

在自顶向下的方法中，我们从一个大问题开始，递归解决较小的子问题。不过，我们必须使用记忆化技术来存储子问题的结果，这样以后就不必重新计算该子问题了。在自下而上的方法中，我们先解决最小的子问题，然后再解决其他更小的子问题。在自下而上的方法中，子问题的结果通常使用多维数组以表格形式存储。

现在，我们将探讨动态程序设计领域的一些实例。有些例子听起来可能与我们日常的编程问题非常相似。我们将从著名的 "knapsack" 问题开始。