什么情况下使用动态规划
满足下面三个条件之一，则极有可能使用动态规划90%-95%：
- 求最大值，最小值
- 判断方案是否可行
- 统计方案个数
极不可能使用动态规划的情况：
- 求出所有具体方案而非方案的个数（要用DFS而不是DP）
- 输入数据是一个集合而不是序列
- 暴力算法已经是多项式级别
DP 擅长将暴力情况下复杂度为O(n!)和O(2^n) 的优化为O(n^2) 或O(n^3) ,
若原本暴力算法就是O(n^2) 或O(n^3) , 则没有多少优化的空间
动态规划的4点要素
- 状态State
灵感，创造力，存储小规模问题的结果
- 最优解 / Maximum / Minimum
- Yes / No
- Count(*)
- 方程 Function
状态之间的联系，怎么通过小的状态，来求得大的状态 - 初始化 Initialization
最极限的小状态是什么，起点 - 答案 Answer
最大的那个状态是什么，终点
常见的动态规划类型及状态特点
坐标型，单序列，双序列，划分型，背包型，区间型，博弈型
