1. 哪些 问题可以用动态规划
最优子结构：原问题的最优解包含子问题的最优解
子问题重叠：例如：斐波那契数列（非必须）
无后效性：比如F(4)不会用到F(6)的值。
## 2. 常用动态规划的模板有哪些
### 2.1. 背包问题：
#### 2.1.1. 01背包
#### 2.1.2. 完全背包
#### 2.1.3. 多重背包
### 2.2. 线性DP
#### 2.2.1. 超级楼梯：M级台阶，一次走1或2级，由多少不同走法
dp[1] = 0
dp[2] = 1
dp[3] = 2
求解方法：
- 递归
- 记忆化递归（将结果存在数组里面）
- 动态规划，直接将结果存在数组中
- 动态规划，迭代（优化空间）
- 动态规划，打表，把所有的值都求出来，适用于多次查询的情况，全部存在数组
2.3. 区间DP
2.4. 树形DP
2.5. 数位DP
2.6. 状态压缩DP
2.7. 插头DP
3. 动态规划求解的秘籍
状态，阶段，决策
3.1.1. 状态转移方程
- 找目标的上一个状态
- 从上一个状态转移到当前状态
- 初始化（给初值，比如dp[1] = 0）
- 求解目标是什么
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。也可以邮件至 2738430398@qq.com