数据结构与算法_动态规划（DP）

    《Dynamic Programming》中的 “Programming”  不是编程的意思，而是一种表格处理法。我们把每一步得到的子问题结果存储在表格里，每次遇到该子问题时不需要再求解一遍，只需要查询表格即可。

    动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干干子问题，自顶向下求解各个子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原问题分解为若干子问题，然后自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

使用动态规划求解的基本条件：

    （1）最优子结构

        最优子结构性质是指问题的最优解包含其子问题的最优解。最优子结构是使用动态规划的最基本条件，如果不具有最优子结构性质，就不可以使用动态规划解决。

    （2）子问题重叠

        子问题重叠是指在求解子问题的过程中，有大量的子问题是重复的，那么只需要求解一次，然后把结果存储在表中，以后使用时可以直接查询，不需要再次求解。子问题重叠不是使用动态规划的必要条件，但存在子问题重叠更能够充分彰显动态规划的优势。

          例如下面的斐波那契数列，大量子问题重叠

    （3）无后效性

        动态规划是将原问题分解为若干个重叠子问题，每个子问题的求解过程作为一个阶段，完成前一个阶段后，根据前一个阶段的结果求解下一个阶段。当前阶段的求解只和前面阶段有关，和后续阶段无关，称为" 无后效性" 。

        动态规划的状态空间构成一个有向无环图，图中结点对应问题的 “状态”，图中的边对应状态之间的 “转移”，选择向哪个结点转移就是 “决策”。递归式实际上就是 “状态转移方程” 。

    求解动态规划问题，如何确定状态和转移方程是关键，也是难点。不同的状态和转移方程可能导致不同的算法复杂度。

    遇到一个实际问题，如何采用动态规划来解决呢？

        （1）分析最优解的结构特征。

        （2）建立最优值的递归式。

        （3）自底向上计算最优值，并记录。

        （4）构造最优解。