算法导论_15.3 动态规划基础_最优解的值和最优解的区别

15.3 动态规划基础

算法导论中将动态规划的设计分为4个步骤：
1） 描述最优解的结构；
2） 考虑自顶向上递归定义最优解的值（递归算法）；
3） 使用表格自底向上计算最优解的值（动态规划）；
4） 由计算的结果构造一个最优解；
区分：最优解和最优解的值；
最优解：即方案；
最优解的值：这个方案带来的最优值；
第1-3步构成动态规划解的基础，如果只是求最优解的值，可以略去第四步；如果要求求得最优解，需要求解第4步；求解第4步，有时需要在计算第三部的时候记录一些附加信息，方便解出第4步；

什么样的最优化问题适合采用动态规划方法求解：
这个最优化问题应该具有以下两个要素，适合使用动态规划求解：
1） 最优子结构。具有最优子结构的性质，是采用动态规划求解的前提；一个问题具有最优子结构，动态规划是适用的，但是贪心算法也可能适用；
2） 重叠子问题。 不具有重叠子问题性质，那么这个最优化问题可以使用自顶向下的递归方法求解； 具有重叠子问题性质， 采用自顶向下的递归求解，会重复计算相同的子问题，这时候应该选用自底向上的动态规划求解；
递归算法不能解决重叠子问题， 动态规划能够解决重叠子问题；
动态规划与分治算法的区别：
分治算法：子问题都是独立的，解得各个子问题的解，然后合并子问题的解，就是原问题的解；分治算法的一个表现就是递归；
动态规划：子问题不是独立的，子问题之间可能包括相同的公共子子问题，此时如果使用分治算法，会做重复的工作。动态规划对每个子子问题求解一次，将子子问题的解存储在一张表格中，当第二次求解子子问题的时候，直接通过查表得到子子问题的解；
一个最优值可能存在多个解；（解释：获得最优值可能存在多个方案）

一、最优化结构

动态规划的第一步：描述最优解的结构
定义：一个问题的最优解中包含了子问题的最优解，则该问题具有