动态规划题目特点
类型
1. 计数
- 有多少种方式走到指定位置
- 有多少种方法选出k个数使得和是Sum
2. 求最大最小值
状态转移方程：++型
- 从左上角走到右下角路径的最大数字和
- 最长上升自序列长度
3.求存在性
状态转移方程：and or 型
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和是Sum
组成部分
确定状态
- 最后一步：最优策略的最后一步（例如：最后一枚硬币）
- 子问题：问题与原问题一样，但是规模小（最少硬币拼出最小的面值27-Ak
转移方程
- F[X] = min{ F[X-2]+1, F[X-5]+1, F[X-7]+1}
初始条件和边界情况
- 设置初始条件：用转移方程算出来，常见的：F[0]=0
- 边界情况处理：如果不能拼出Y，则F[Y] = 正无穷
计算顺序
一般情况：从小到大，从左到右，从上到下
