基本思想

    动态规划是针对一类求最优解的问题的算法 其核心是将一个问题分解成为若干个子问题，部分类似于分治的思想，通过求每一次的最优决策，来得到一个最优解。

适用条件

1.具有相同的子问题

    我们必须保证我们分割成的子问题也能按照相同的方法分割成更小的自问题， 并这些自问题的最终分割情况是可以解决的。

2.满足最优子结构

    一个决策的子决策也是最优的

3.无后效性

    要求每个子问题的决策不能对后面其他未解决的问题产影响， 如果产生就无法保证决策的最优性， 这就是无后效性。往往需要我们找到一个合适的状态。 

解题步骤

1.确定子问题

    重点是分析哪些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。 

2.确定状态

    根据上面找到的子问题来分割子问题限定状态 

3.推导出状态转移方程

    这里要注意状态转移方程是不是满足所有的条件， 注意不要遗漏。 

4.确定边界条件

    先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不能也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系， 但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）; 

5.确定实现方式

6.确定优化方法

    首先考虑降维问题（优化内存），优先队列、四边形不等式（优化时间）等等。

常用方法

1.模型匹配法

    熟练记忆并且理解LIS、LCS、01背包、完全背包、区间模型、树状模型，基本就是将原模型加以变化后加以套用。

2.三要素法： 

    确定阶段、 确定状态、确定决策

3.寻找规律法

4.边界条件法

5.增加约束条件法