Dynamic Programming

很有可能使用动态规划的情况：

1. 求最大值最小值

2. 判断是否可行

3. 统计方案个数

不使用动态规划的情况：

1. 求出所有具体的方案而非方案 个数

2. 输入数据是一个 集合 而不是 序列

3. 暴力算法的复杂度已经是多项式级别

   1. 动态规划擅长于优化指数级别复杂度（2^n,n!）到多项式级别复杂度(n^2,n^3)

   2. 不擅长优化n^3 到n^2

动态规划四要素 vs 递归 三要素

状态 state

灵感 创造力，储存小规模问题的结果

方程 function

状态之间的联系，怎么通过小的状态来算大的状态

初始化 initialization

最极限的小状态是什么，起点

答案

最大的在那个状态是什么 终点

递归三要素

定义(状态)

1. 接受什么参数

2. 做了什么事

3. 返回什么值

拆解（方程）

1. 何如将参数变小

出口(初始化)

1. 什么时候可以直接return

初始化一个二维的动态规划数组时，先初始化第0行 第0列