动态规划，主要用于解决包含较多重复子问题的最优化问题，当然解决一些包含递归思想的问题时也可以使用动态规划。课程主要讲了“最短路径”，“矩阵链乘”，“最长公共子串”，“多边形剖分”，“0/1背包问题”，“最优化二叉搜索树”等问题。
动态规划概述
使用对象
（一类优化问题 ：）可分为多个重复子问题，子问题的解可以被重复利用。
括号括起来是想说明，不一定是只解决优化问题的。如果一个问题包含重复子问题且能够递归求解时，可以考虑用动态规划方法。
动态规划特点：
-
将原始问题化为一系列子问题（这些子问题有重叠情况）
大问题分割为小问题。
往往大问题包含很多步，而小问题则是指具体考虑一步的情况。
分割例子：
-
最短路径，大问题是考虑从起点到终点的最短，子问题划分可以一步一步考虑（可能使用递归思想），首先考虑为从起点到第一个可能到达点的距离与到达点到终点距离和，取其中的最小值即为最短距离。
-
矩阵链乘，大问题是考虑整个矩阵链中各矩阵的计算顺序；子问题划分是每次把大问题分为两个小问题，查看子问题的复杂度；划分为两个子问题有n中划分，取其中代价最小的作为最佳划分；如此递归下去，就能保证大问题一步步从下往上被计算出来。
-
最长公共子串：大问题是找到两个长度分别为m和n的串中公共的子串；划分时从后往前考虑，如果两个串的最后一个字符相同，那么这个字符必然是公共子串，则大问题划分为找长度为m-1和n-1的串的公共子串，且结果再加上这个相同的末尾字符；如果不同，则又分为两种情况：如果m的串的末尾字符不是公共字符，那么问题划分为求长度为m-1和n的两个子串的公共子串；如果n的串的末尾字符不是公共子串，那么问题划分为找长度为m和长度为n-1的两个公共子串，最终的结果就是取这两种情况中最长的。这里的划分还是需要学习或者记忆的。
-
多边形的三角剖分 ，大问题是将多边形划分为不相交的三角形的弦的集合；子问题划分与矩阵链乘一致，在第一个顶点和最后一个顶点间选择一个顶点，将多边形划分为两个小多边形和一个三角形。
-
0、1背包问题，大问题是在背包容量一定每件物品只能取或不取的情况下选择物品使背包中的物品价值最大；子问题把问题将每个物品取或不取使用0、1来表示，则n个物品对应n个布尔序列。定义子问题为“在背包容量为j，从i到n的剩余物品中选择物品使背包价值最大”，通过该定义，整个问题能够用相同的形式表示，使得存在重复子问题（剩余物品相同情况下背包容量相同的情况）实在巧妙。
-
最优化二叉搜索树 ， 待编辑
-
-
子问题只求解一次，并将结果保留下来，重复使用时直接使用该值
这是动态规划真正快的原因。有了上述子问题的定义，我们发现较大问题的解决需要较小问题先被解决，且各个较大的问题往往需要的小问题有重叠。这时如果用递归，这些问题会被重复计算，并不能提升效率；使用动态规划，我们常常将子问题的解存储在一个矩阵中，这样加大问题需要这些子问题的解时，直接从矩阵中获得结果即可，而不必再次计算之前已经被计算过的子问题。
-
自底向上地计算
使用动态规划，我们分析解的依赖结构，由下往上地计算较小问题。小问题的解构成大问题的解，最终得到需要的结果。
动态规划思路
由上，我们可以给出一些使用动态规划的思路：
-
找到问题的优化子结构，这往往是使用递归的思想，将大问题划为一步步的小问题，递归求解。
-
找到子结构后，分析解的依赖情况（往往在矩阵中画出计算顺序，便于直观地找到计算方法），设计出使用循环的方法去计算解
-
在计算解的过程中往往需要保留一些解的相关信息
这通常是由于问题的需求导致的。我们可能想要一个最短的路径，而动态规划的优化往往只能是求一个最小的路径代价，所以在求解最小路径时，往往需要记录得到该代价的路径。
总的来说，动态规划是自上而下地考虑问题（准确的说是考虑一步一步递归考虑），但自底向顶的计算问题。与分治的不同之处，就是它的之问题是有重叠的。
解体步骤（思考步骤）
-
找问题的优化子结构(Optimal substructure)，并常常使用反证法来证明该结构能够得到最优解
-
描述该优化子结构有重叠子问题，通常是画一个树形图
-
递归定义最优化的解，给出形式化的解结构
相比第一步，更加地形式化。即用数学公式的形式给出，并注意边界条件的定义。
-
给出算法
-
时间复杂度、空间复杂度的分析