【超详细】动态规划到底在做什么？何时去用？

动态规划算法dynamic programming

Bellman-Ford单源最短路径的算法

即便你不知道动态规划也有可能在使用

斐波拉且数列 ，1，1，2，3，5

可以使用递归，找到子问题的答案，所有的父问题也就被实现了

如果使用动态规划

micro second

子问题被解决时会有规划地存储，下次需要时进行查表。

动态规划本身不是一种具体地算法，而是一种接菌最优化问题地思想或者方法。

分而治之求他的子问题，

递归 缓存之前地状态。

将一个问题分解成多个子问题，再次面对这个问题时不用再进行计算，

不同子问题或者状态转移地关系我们把它叫做状态转移方程，。

什么样特征的问题适合使用该方法

拥有最优子结构。

1.可以写出状态转移方程

2.我们需要边界条件

（没有无限的递归和不溢出的栈）

当我学习知识，需要结合现实的应用。

0<交易次数<=2

典型的动态规划。

暴力解法四个for循环。

缓存子问题的状态。

不错过每一个赚钱的指挥。最后一天还有一个全局的视野Bellman方程 ，可以铭记历史

一共有几个状态

buy1 sell1

buy2 sell2

使用两个二维数组。

时间维度，状态维度

class Solution：

def maxProfit

写出状态转移方程和边界条件。

第一天是没有对比的。

trade1[0][0],trade1[0][1]=-prices[0],0

trade2[0][0],trade2[0][1]=-prices[0],0

可以缓存之前的状态。

拿空间去换取时间的算法。可以大幅度的降低时间的复杂度。

官方的解法可以进行状态压缩 节省内存