1. 分解成重复子问题

2. 找最优子结构

- 自顶向下(以Fibonacci为例，从最上面往下推导，先找f(n),然后依次找f(n-1)，f(n-2)，最后找到f(1),这种比较符合人脑思维)，这种一般是递归+记忆化搜索(就是所谓的加缓存)。

- 自底向上(从最下面往上推到，先找到f(1),f(2)，以这两个为基础推导到f(n)，这个一般是计算机执行方式，也就是递归执行路径)，因为递归其实也就是迭代for loop，自底向上就是直接for loop，用已知的值推导出未知的值，然后一直递推。

1. 最优子结构 opt[i,j]=best_of(opt[n-1],opt[n-2],....)

2. 存储中间状态：opt[i]

3. 递推公式：（美其名曰：状态转移方程或者DP方程）

Fib:opt[i]=opt[i-1]+opt[i-2]

二维路径：opt[i,j]=opt[i+1,j]+opt[i,j+1]（需判断a[i,j]是否为空地）

1. 打破自己的思维惯性，形成机器思维。（机器思维->找重复性）

2. 理解复杂逻辑的关键。

3. 也是职业进阶的要点要领。（不要凡事亲力亲为，要放权给下面人做，允许下面人犯错）

动态规划这块内容，感觉真的不好理解，这周课程的每个视频我平均看了4-5次，才大概理清动态规划的工作原理。这个很考验抽象功底啊，很多问题都需要抽象出一定的东西在进行动态规划，现在做题除了二维矩阵，其他我都感觉抽象不出来。

我理解动态规划可以由递归分治推导而来，加上一定的缓存（记忆化搜索），然后可以慢慢弄出来动态规划的方程。但是这种**自顶向下**的方式其实是很低效的，符合人脑思维，但是实质还是递归/分治+缓存。而真正的动态规划一定是**自下而上**，直接由已知数值推导出目标参数，直接for loop往上推。（**这个很考基本功啊，递归不太行基本懵逼，多练才是正途**）

这两天做题，总结了下动态规划解题思路：

1. **寻找重复性，最优子结构**：这个不一定是固定的，可能还会根据不同条件去分情况讨论。(比如编码那道题)

2. **定义状态数组**：这个除了有的题不好定义，一般根据参数是什么就定义什么，比如矩阵就二维，但我感觉比较有问题的点是一些数组的初始值定义，初学者总会出问题。

3. **定义状态转移方程**：大部分的题，第一个最优子结构找出来，状态转移方程基本就定好了。

动态规划的题，数组的下标，感觉很容易出问题，稍不注意就下标越界。

这块题做和消化都要花挺长时间的，而且题还很很多，后续要多花点精力在这边，把没做完的题刷完。