动态规划（Dynamic Programming）

1. 递归+记忆化 --> 递推

2. 状态的定义：opt[n], dp[n], fib[n]

3. 状态转移方程：opt[n] = best_of(opt[n-1], opt[n-2], …)

4. 最优子结构

传统的斐波那契数列的解法，时间复杂度O（2^N)，使用简单的递归算***有很多的冗余计算

使用内存数组进行记忆化，降低时间复杂度到O（N）

使用递推，从下往上推，也会快速很多

从左上角走到右下角有多少种走法？

可以看做是往下走到达终点的走法数+往右走到达终点的走法数

这种方法跟斐波那契数列一样，会产生大量重复计算的问题，解决办法还是加上存储
如果使用递推，就从下往上开始走，反着进行

这里写出状态转移方程

含义就是，ij格子到达终点的方法数，等于右边格子的方法数加上下边格子的方法数之和，那么我们就可以填满整个图

时间复杂度为O（MN)

总结：

最优子结构：通过求解原生问题，同时能够解决很多的子问题（例如从别的起点到终点有多少种），也就是说每个节点的结果只需要依赖前一个或几个节点的结果即可

动态规划 vs 回溯 vs 贪心