Dynamic Programming（动态规划）
面试级别的算法中最难的内容了，没有完全的形式或模板或者指导原则
- 最高原则：由小推大
- 一般是一维数组或者二维矩阵的推导
- 状态转移方程找到了，DP的题基本就解出来了百分之七十
- 也有不按坐标顺序的纯逻辑递推，例如Longest Increasing Matrix Path（滑雪问题），但实际上还是由小推大的方式
- 代码一般不长，逻辑上很少有特殊细节需要处理，但是你就是想不到答案_(:зゝ∠)_
- DP总体而言分为接龙类，区间类，博弈类，匹配类
总结目前碰到过的最难的动态规划题
- K sum （三维的背包问题，状态的初始化很需要思考一下）
- Minimum adjustment cost（特殊的条件导致了一个很特殊的空间时间复杂度的诞生，初始条件的值也非常迷）
- Scramble String（四维的DP首先已经很恐怖了，还需要找到一个优化的方式将空间降至三维，对于字符串的替换与否的两种逻辑，边界条件非常容易出错）
- K edit distance（Trie树和DP的结合本身就不是一个易与的东西，Trie树的结构又是一个很头痛的事）
- LIS（O(n^2)的算法不是秘密了，但是O(nlgn)的算法绝对不是一下想得出来的）