动态规划
本质是什么？ 解决重复运算 什么重复？ 树形重复
DP三步走
- 画出搜索树
- 根据节点语义找出cache
- 推导出状态转移方程
动态规划的中心思想是，面对 search tree 里都是 "overlap subproblem"，如何根据问题结构制定缓存策略，避免重叠问题重复计算。
循环求解的方法 四个步骤
- 状态定义 state (相当于递归函数的传入参数和返回值的意义)
- 初始化， 从什么地方开始，哪些状态不是通过推导得来的，一眼看出来是什么值。
- 循环递推求解，怎么算
- 求结果，终点在哪
什么题极有可能是用DP：
Maximum/Minimum Yes/NO Count
最优方案
输入数据是有序的
什么情况不能用DP 求所有的具体方案 输入是一个集合而不是序列
关于贪心
极少有题是用贪心来求解，这种题很难出 难就难在你要证明贪心是对的。 大部分你能想到的贪心都是错的。Jump
分治法和动态规划的区别
分治法往下分的时候是不会分出同样的东西来的。比如二叉树
但是动归会有重复的子问题，才有空间换时间的可能性，需要记录中间的过程。
动归的思想是：大规模的问题是由小规模的问题的结果运算而来的。 什么是大规模的问题，就是问题的终点。 小规模的问题，是一眼就看出来结果的问题。
有循环依赖的情况，不能用动态规划。动态规划一般是有一个固定方向去前进的。
二维数组
网格类的题目 正方形用右下角作为定位角 长方形可以用左上角和右下角作为定位角。
例题：
Maximal Square
如何从五个for循环，优化到两层for循环的。
if (matrix[i][j] == 1)
f[i][j] = min(LEFT[i - 1][j], UP[i][j-1], f[i-1][j-1]) + 1;
if (matrix[i][j] == 0)
f[i][j] = 0;
如何优化二维DP的空间
使用滚动数组
一个转移方程的是
f[i][j] = f[i - 1][j] + f[i][j - 1]
可以发现第i层和第i-2层没什么关系了，这种情况下 i-2 层可以重复利用。对第一维取模就可以了。
f[i % 2][j] = f[(i - 1) % 2][j] + f[i % 2][j - 1]
为什么不能对j取模？用上一行来推导下一行。
例题：
Longest Increasing Continuous subsequence II
Paint House
题意：没有两个相邻的房子是同样的颜色。
因为直到房子i，其最小的涂色开销是直到房子i-1的最小涂色开销，加上房子i本身的涂色开销。所以这道题使用dp来解。
但是房子i的涂色方式需要根据房子i-1的涂色方式来确定，所以我们对房子i-1要记录涂三种颜色分别不同的开销，这样房子i在涂色的时候，我们就知道三种颜色各自的最小开销是多少了。
空间上：我们在原数组上修改，可以做到不用空间。
Paint House II
和第一题思路差不多。但是由于有K种颜色，不能简单的用Math.min，我们可以遍历一遍找到除了自己以外最小的颜色。所以记录下最小的颜色和次小的颜色就可以了。
注意：维护的是最小的和次小的颜色。别忘了去更新次小的颜色。