动态规划总结

一般用dp 解的几类问题：

1. 计数：

（1） 多少种方法到右下角
（2） 多少种方法使和为sum

2. 求最大最小值：

（1） 从左上到右下的最大数字和
（2） 最长上升子序列长度

3. 求存在性：

（1） 取石子，先手是否必胜
（2） 能不能选出k 个数使和为sum

二． 解题步骤：

1. 定义状态：（一维还是二维，有几个变量）

（1） 看最后一次选择
（2） 前边怎么和最后一次拼起来

2. 状态转移方程

3. 初始化条件和边界（小技巧：初始化放在for 循环中）

4. 考虑状态压缩

一维压缩成两个变量的滚动数组
二维压缩成一维后大都是从后往前遍历