Dynamic Programming Summary

动态规划题目特点

1. 计数
   • 有多少种方式走到右下角
   • 有多少中方法选出 k 个数使得和是 Sum
2. 求最大最小值
   • 从左上角走到右下角路径的最大数字和
   • 最长上升子序列长度
3. 求存在性
   • 取石子游戏，先手是否必胜，博弈
   • 能不能选出 k 个数使得和是 Sum

动态规划四个步骤：

1. 确定状态
   开数组的意义
   确定状态需要两个意识：
   • 最后一步
     最后策略中的最后一个
   • 子问题
     从后往前推子问题，问题规模渐渐变小
2. 转移方程
3. 初始条件和边界情况
   转移方程算不出来的，需要手工去定义的 （细心考虑周全）
4. 计算顺序
   转移方程的计算 （利用之前的计算结果）