動(dòng)態(tài)規(guī)劃算法dynamic programming

Bellman-Ford單源最短路徑的算法

即便你不知道動(dòng)態(tài)規(guī)劃也有可能在使用

斐波拉且數(shù)列 ，1，1，2，3，5

可以使用遞歸，找到子問題的答案，所有的父問題也就被實(shí)現(xiàn)了

如果使用動(dòng)態(tài)規(guī)劃

micro second

子問題被解決時(shí)會(huì)有規(guī)劃地存儲(chǔ)，下次需要時(shí)進(jìn)行查表。

動(dòng)態(tài)規(guī)劃本身不是一種具體地算法，而是一種接菌最優(yōu)化問題地思想或者方法。

分而治之求他的子問題，

遞歸 緩存之前地狀態(tài)。

將一個(gè)問題分解成多個(gè)子問題，再次面對(duì)這個(gè)問題時(shí)不用再進(jìn)行計(jì)算，

不同子問題或者狀態(tài)轉(zhuǎn)移地關(guān)系我們把它叫做狀態(tài)轉(zhuǎn)移方程，。

什么樣特征的問題適合使用該方法

擁有最優(yōu)子結(jié)構(gòu)。

1.可以寫出狀態(tài)轉(zhuǎn)移方程

2.我們需要邊界條件

（沒有無限的遞歸和不溢出的棧）

當(dāng)我學(xué)習(xí)知識(shí)，需要結(jié)合現(xiàn)實(shí)的應(yīng)用。

0<交易次數(shù)<=2

典型的動(dòng)態(tài)規(guī)劃。

暴力解法四個(gè)for循環(huán)。

緩存子問題的狀態(tài)。

不錯(cuò)過每一個(gè)賺錢的指揮。最后一天還有一個(gè)全局的視野Bellman方程 ，可以銘記歷史

一共有幾個(gè)狀態(tài)

buy1 sell1

buy2 sell2

使用兩個(gè)二維數(shù)組。

時(shí)間維度，狀態(tài)維度

class Solution：

def maxProfit

寫出狀態(tài)轉(zhuǎn)移方程和邊界條件。

第一天是沒有對(duì)比的。

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

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

可以緩存之前的狀態(tài)。

拿空間去換取時(shí)間的算法?？梢源蠓鹊慕档蜁r(shí)間的復(fù)雜度。

官方的解法可以進(jìn)行狀態(tài)壓縮 節(jié)省內(nèi)存