01、动态规划的基本思想

动态规划算法的思想比较简单，其实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将待求解问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。

每种算法都有自己的特点。贪心法的当前选择可能要依赖于已经做出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是自顶向下，一步一步地作出贪心选择，但如果当前选择可能要依赖子问题的解时，就难以通过局部的贪心策略达到整体最优解。分治法中的各个子问题是独立的 (即不包含公共的子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成原问题的解。但如果各个子问题是不独立的，则分治法要做许多不必要的工作，即重复地解公共的子问题，对时间的消耗太大。

适合采用动态规划法求解的问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。这样就避免了大量的无意义的重复计算，从而降低算法的时间复杂性。如何对已解决的子问题的解进行保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都将其计算结果填入该表，需要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式。
【例1】Fibonacci数列如表1所示。

表1Fibonacci数列

Fibonacci数列的递归定义式如下：

设n=4，则F(4)的求解过程可表示为一棵二叉树，如图1所示。

■ 图1F(4)的求解过程

在图1所示中，同种阴影表示相同的子问题，即说明F(4)划分的两个子问题F(3)和F(2)不是相互独立的。若采用自顶向下的递归求解，F(2)子问题重复计算。如果n=5，则F(3)和F(2)两个子问题会重复计算。以此类推，n越大，重复计算现象越严重，影响求解效率。

动态规划在求解过程中采用一维数组a存放各个子问题的解。首先，将F(1)和F(0)的解存于a［0］、a［1］中，如表2所示；然后在求解F(2)时，由于F(2)=F(1)+F(0)，因此只需直接从数组a中取出F(1)和F(0)的值计算即可，并将F(2)的值存入a［2］中，如表3所示；接下来求解F(3)时，只需从数组a中取出F(2)和F(1)的值直接对F(3)进行求解，并将求得的值存入a［3］中，如表4所示；最后，在求解F(4)时，从数组a中取出F(3)和F(2)的值直接对F(4)进行求解，并将求得的值存入a［4］中，如表5所示。

由此可见，动态规划的关键在于解决冗余，将原来具有指数级复杂性的搜索算法改进成具有多项式时间的算法，这是动态规划算法的根本目的。其实，动态规划是对贪心算法和分治法的一种折中，它所解决的问题往往不具有贪心实质，但是各个子问题又不是完全零散的。在实现的过程中，动态规划方法需要存储各种状态，所以它的空间复杂性要大于其他的算法，这是一种以空间换取时间的技术。