# Road Map
# 动态规划
动态规划（Dynamic Programming）是一种分阶段求解策略问题的数学思想。
动态规划中包含三个重要概念：最优子结构、边界、状态转移公式。
- 最优子结构，求解一个问题时，首先要找出问题的最优子结构；
- 边界，边界是最简的最优子结构，无需再简化便可得到结果；如果一个问题没有边界，将无法得到有限的结果；
- 状态转换方程，是阶段与阶段直接的转换关系
动态规划类似于高中数学的数学归纳法
# 求解过程
确定状态
研究最优策略的最后一步，转化为子问题，定义最优子结构
转换方式
根据子问题定义和最后一步求解过程，抽象出状态转换方程
初始条件和边界情况
细心，考虑周全
计算顺序
利用之前的计算结果
# 动态规划题目特点
求方案数（计数）
- 有多少种方式走到右下角
- 有多少种方法选出 k 个数使得和为 sum
求最值
- 从左上角走到右下角路径的最大数字和
- 求最长上升子序列的长度
求存在性
- 青蛙过河，能否跳到最后一个位置
- 取石子游戏，先手是否必胜 - 博弈论
- 能不能选出 k 个数使得和是 sum
# DP 分类
- 记忆化搜索
- 背包 dp
- 区间 dp
- 树形 dp
- 状压 dp
- 数位 dp
# 其他
- 插头 dp
- 计数 dp