动态规划算法的基本思想与分治法类似，是将一个待解决的大问题分解成若干规模较小的子问题，先求解各个子问题，然后依据子问题的解得到原问题的解。但是，适用动态规划算法求解的问题，经分解得到的子问题一般不是相互独立的，也就是说，这类问题具有最优子结构性质和重叠子问题性质。在这样的过程中自然引出递归算法。 

本章首先结合范例介绍最优子结构性质，递归地定义最优值，以及构造最优解。然后，分析子问题的重叠性质。为了克服子问题被反复计算的特征，动态规划算法对每个子问题仅计算一次，并将解保留，当再次需要解词子问题时，只要用常数时间查找解救可以了。在此，介绍了备忘录方法。 

1、 理解动态规划算法的概念。

2、 掌握动态规划算法的基本要素：1）最优子结构性质；2）重叠子问题性质。

3、 通过范例学习动态规划算法的设计方法。应用范例包括： 1）矩阵连乘问题；2）最长公共子序列问题； 3）流水作业调度；背包问题； 4）背包问题。 

重点：要正确把握动态规划算法的特征，对于具有最优子结构和重叠子问题性质的问题，运用动态规划算法求解的效率是良好的。针对具体问题，学会实现动态规划算法。

难点：分析问题是否具有最优子结构和重叠子问题性质，针对具有这两个性质的问题，遵循动态规划算法的设计步骤，设计有效的算法。

动态规划算法适用于解最优化问题，掌握算法设计的步骤： 1） 找出最优解的性质，并刻画其结构特征； 2） 递归地定义最优值； 3） 以自底向上的方式计算出最优值； 4） 根据计算最优值的过程中得到的信息，构造最优解。 

最优子结构性质，重叠子问题性质，动态规划算法，备忘录方法。