动态规划理论基础-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划理论基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

定义

动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解(an optimal solution)，而不是最优解(the optimal solution)，因为可能有多个解都达到最优值。

动态规划与分治问题的区别

分治问题：将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。

与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题(子问题的求解是递归进行的，将其划分为更小的子子问题)。
在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。

而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

两种方式实现动态规划

根据是否将子问题的解保存到一个表中，分出两种实现动态规划的方式。

方法一：带备忘录的自顶向下法

此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间，否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized),因为它“记住”了之前已经计算出的结果。