【从零开始学习计算机科学】算法分析（三）动态规划 与 贪心算法

动态规划

动态规划通过组合子问题的解而解决整个问题的。相对动态规划，分治算法是指将问题划分为一些独立的子问题，递归的求解各个问题，然后合并子问题的解而得到原问题的解。例如归并排序，快速排序都是采用分治算法思想。而动态规划与此不同，动态规划适用于子问题不是独立的情况，也就是说各个子问题包含有公共的子问题。在这种情况下，用分治算法则会重复做不必要的工作。而采用动态规划算法对每个子问题只求解一次，将其结果存放到一张表中，以供后面的子问题参考，从而避免每次遇到各个子问题时重新计算答案。因此，我们可以得出动态规划与分治法之间的区别主要是，分治法是指将问题分成一些独立的子问题，递归的求解各子问题，而动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题。

动态规划通常用于最优化问题（此类问题一般有很多可行解，我们希望从这些解中找出一个具有最优（最大或最小）值的解）。
动态规划算法的设计分为以下四个步骤：描述最优解的结构，递归定义最优解的值，按自低向上的方式计算最优解的值，由计算出的结果构造一个最优解。
动态规划的第一步是描述最优解的结构，即选择问题的在什么时候会出现最优解，通过分析子问题的最优解而达到整个问题的最优解。在第二步，递归定义最优解的值，根据第一步得到的最优解描述，将整个问题分成小问题，直到问题不可再分为止，层层选择最优，构成整个问题的最优解，给出最优解的递归公式。第三步根据第二步给的递归公式，采用自底向上的策略，计算每个问题的最优解，并将结果保存到辅助表中。第四步骤是根据第三步中的最优解，借助保存在表中的值&#