Tag VII. Dynamic Programming

3. 在分治的基础上优化，用一个hashmap记录之前已经得到的值，就不用再分治再展开了，因为要用的结果是一样的。时间复杂度是O(n^2)

二叉树的时间复杂度计算 = 节点个数 X 每个节点上的耗费

所以二叉树一般都是 O(N) = N x O(1)

递归2^N + hash memoriztion记忆化搜索 == 动规 N^2

所以这个优化了的triangle的时间复杂度就是 n^2 个点(指的是数量级)，每个点被访问2次，每个点的耗费是O(n) 。finally, O(N^2)

4. 所以，动规就是浪费了一点空间用hash表记下来把中间的结果保存起来以后用，有重复的中间结果的计算。所以会比分治递归快一点。但不是所有的分治都可以。

注意：二叉树就不是动规，因为它没有重复的点，没有可优化的余地。

动规所有的题都没有一个通用的框架，它是一种思想，在算法之上的思想。

5. 动规的实现方式：

多重循环(常见但思考有难度，边界容易错)

记忆化搜索(有些面试官不知道 优点 容易从搜索算法直接转化过来 缺点递归)

8. 动态规划的四个要素：

I. State 状态 (存储小规模问题的结果 x y是什么)

II. Function方程 (状态之间的联系，怎么通过小的状态 算大的状态)

III. Initialization初始化(起点 以及能直接得到的结果， 或者不好用方程算的边界)

IV. Answer 答案 (最后要的结果的终点)

9. 面试中的常见动态规划类型：

坐标型 15%

序列型 30%

双序列 30%

划分型 10%

背包型 10%

区间型 5%

10. 使用动规三个条件：极有可能

求最大值最小值

判断是否可行

统计方案个数

*复习：什么情况使用二分法：log n 的程序、

什么时候分治法：大部分的二叉树都可以

11. 什么情况不适用动规：

求所有具体方案而非方案个数 DFS做

输入的数据是一个集合而不是一个序列（除了背包的动规，其他的都要满足有序）

如果一个题用暴力法已经是N^2了，那就不用动规了。

12. 分类题型总结：

1）坐标型：

f[x][y] 从起点开始走到x, y

function[x][y]走到x y 之前的一步存的结果