动态规划（DP）
使用条件
- 最优化原理 : 具有最优子结构的性质，一个问题的最优解只取决于子问题的最优解
- 无后效性 ：某阶段的状态一旦确定，则此后的演变过程不再受此前各状态和决策的影响
使用步骤
- 划分阶段
- 确定状态和状态变量
- 确定决策并写出状态转移方程
- 寻找边界条件
- 设计并实现程序
两种方式
- 递推 ：从前往后
- 递归（记忆化搜索）：从后往前
不适合用动态规划的情况
- 不能划分阶段的题
- 不符合最优化原理的题
- 不具备无后效性原则的题
线性DP
- 线性动态规划的目标函数为特定变量的线性函数。
- 约束是这些变量的线性不等式或等式。
- 目的是求目标函数的最大值或最小值。
区间DP
- 先算出小区间的最优解，再去得到大区间的最优解。
- 用状态f[i][j]表示区间[i,j]的最优解。
- f[i][j]可以由[i,j]的子区间 ([i,k],[k,j]) 得到。
