动态规划算法最大的特性是：局部最优中产生整体最优。具体方法是：逐层迭代，从局部开始，一步一步走到整体。

用动态规划求解最优化问题的第一步是描述最优解的结构，如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构

当一个问题具有最优子结构时，我们才可以在分治法、动态规划、贪心策略等算法中进行选择

在动态规划中，我们利用子问题的最优解来构造问题的一个最优解

寻找最优子结构时，可以遵循一种共同的模式：

1. 问题的一个解可以是做一个选择，如选择一个前一个装配站或者选择一个下标以在该位置分裂矩阵，选择完成后会得到一个或多个子问题
2. 假设对一个给定的问题，一直的是一个可以导致最优解的选择，我们不必去关系如何确定这个选择，只要假定它是已知的（与数学上的归纳证明方法是类似的）
3. 在已知这个选择后，要确定那些子问题会随之发生，以及如何最好的描述所得到的子问题空间
4. 利用一个“剪贴”（cut-and-paste）的技术，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的，通过假设一个子问题的解都 不是最优解然后导出矛盾即可

动态规划以自底向上的方式来利用最优子结构，也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解，寻找问题的最优解需要在子问题中作出选择，即选择将用哪一个来求解问题

适用于动态规划方法求解的问题必须具有的第二个条件就是子问题空间要“很小”，也就是用于解决原问题的递归算法可以反复解决同样的子问题，而不会产生新的子问题，当一个递归算法不断的调用同一问题时，我们就称该问题包含“重叠子问题”，而适用于分治法解决的问题往往在递归的每一步都产生全新的问题。

动态规划总是充分利用重叠子问题，即通过每个子问题只解一次，把结果保存在一个表中，供之后查表，而避免反复进行相同的运算

动态规划有一个变形，他既具有通常的动态规划的效率，又采用了一种自顶向下的策略

其思想是为每一个子问题的解在表中创建一个表项，开始时，每个表项最初都包含一个特殊的值，以表示该表项有待填入，当在递归算法的执行中第一次遇到一个子问题时，就计算他的解并填入表中，以后每次遇到该子问题时只要查看这个表即可

事实上，备忘录方法与动态规划方法的思想是一样的，只是动态规划采用的是自底向上的策略，而备忘录方法则通过递归调用实现自顶向下的策略

欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤