思考路径：
子问题的递归暴力穷举—>剪枝、记忆化搜索—>动态规划
特征：
分治策略
与分治法不同的是，适合动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。
会重复计算。
基本要素构成：
最优子结构（问题的最优解包含了其子问题的最优解）
状态转移方程
重叠子问题
解题步骤：
- 问题拆解，找到问题之间的具体联系
- 状态定义
- 递推方程推导
- 实现
题目类型：
矩阵类动态规划（图、数组）：对于第 i 个位置的状态分析，考虑当前位置及邻近的状态）
序列类动态规划（对于第 i 个位置的状态分析，它不仅仅需要考虑当前位置的状态，还需要考虑前面 i – 1 个位置的状态，其实就是寻找当前状态和之前所有状态的关系）【这种一般是指，要分为区间讨论的，或者有相邻限制的，其实和区间dp是一个意思】『应该不是区间dp吧』
股票
也可以分为线性dp和区间dp，
线性dp一般是在前缀或后缀上转移。
区间dp是指从小区间转移到大区间。其中，分为两种：从两侧向内说小问题规模，也就是两个端点选或不选（最长回文子序列）；第二个则是。分割为规模更小的子区间，枚举看选哪个（1039，堆石子）。