hello大家好 我是大家的學(xué)習(xí)成長(zhǎng)小伙伴Captain

動(dòng)態(tài)規(guī)劃，大家肯定都聽(tīng)過(guò)這個(gè)名詞，這個(gè)是很經(jīng)典的一個(gè)解決問(wèn)題的思路，也是很有技巧的，一般大廠也喜歡問(wèn)這種類(lèi)型的問(wèn)題

今天我們一起來(lái)學(xué)習(xí)一下動(dòng)態(tài)規(guī)劃到底是個(gè)什么

什么是動(dòng)態(tài)規(guī)劃？

動(dòng)態(tài)規(guī)劃（英語(yǔ)：Dynamic programming，簡(jiǎn)稱(chēng)DP）是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。

?

動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題[1]和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。

?

動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。

?

通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量：一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化（en:memoization）存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表。這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。

核心思想

動(dòng)態(tài)規(guī)劃算法是通過(guò)拆分問(wèn)題，定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系，使得問(wèn)題能夠以遞推（或者說(shuō)分治）的方式去解決。

動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。

在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。

按照定義來(lái)看，動(dòng)態(tài)規(guī)劃就是把一個(gè)大問(wèn)題然后拆分成很多小問(wèn)題，這個(gè)本身是沒(méi)啥問(wèn)題的，其實(shí)啊，我個(gè)人覺(jué)得這不是動(dòng)態(tài)規(guī)劃的核心思想

事實(shí)上是任何大問(wèn)題都能拆解成許多小問(wèn)題，一個(gè)大問(wèn)題之所以能用動(dòng)態(tài)規(guī)劃來(lái)解決，并不是因?yàn)樗梢圆鸾獬珊芏嘈?wèn)題，這不是關(guān)鍵

動(dòng)態(tài)規(guī)劃的本質(zhì)不在于是遞推或是遞歸，也不需要糾結(jié)是不是內(nèi)存換時(shí)間，本質(zhì)是解決的這些小問(wèn)題是否能夠被重復(fù)調(diào)用，這就是問(wèn)題是否可以用動(dòng)態(tài)規(guī)劃解決的要素

我們先來(lái)看一個(gè)最熟悉的例子

斐波那契數(shù)列（Fibonacci polynomial）

計(jì)算斐波那契數(shù)列（Fibonacci polynomial）的一個(gè)最基礎(chǔ)的算法是，直接按照定義計(jì)算（函數(shù)遞歸）：

???function?fib(n）???????if?n?=?0?or?n?=?1???????????return?n       return fib(n ? 1) + fib（n ? 2）

當(dāng)n=5時(shí)，fib(5)的計(jì)算過(guò)程如下:

?

fib(5)fib(4)?+?fib(3)(fib(3)?+?fib(2))?+?(fib(2)?+?fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1)?+?fib(0))?+?fib(1))?+?(fib(1)?+?fib(0)))?+?((fib(1)?+?fib(0))?+?fib(1))

由上面可以看出，這種算法對(duì)于相似的子問(wèn)題進(jìn)行了重復(fù)的計(jì)算，因此不是一種高效的算法。實(shí)際上，該算法的運(yùn)算時(shí)間是指數(shù)級(jí)增長(zhǎng)的。

我們可以通過(guò)保存已經(jīng)計(jì)算過(guò)的子問(wèn)題的解來(lái)避免重復(fù)計(jì)算

? ? ? ? ?

再來(lái)看一個(gè)類(lèi)似的例子，青蛙跳臺(tái)階

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) 10 級(jí)的臺(tái)階總共有多少種跳法。

其實(shí)這個(gè)問(wèn)題思路也是比較簡(jiǎn)單的，要想跳到第10級(jí)臺(tái)階，要么是先跳到第9級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第8級(jí)，然后一次邁2級(jí)臺(tái)階上去。

同理，要想跳到第9級(jí)臺(tái)階，要么是先跳到第8級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第7級(jí)，然后一次邁2級(jí)臺(tái)階上去。

要想跳到第8級(jí)臺(tái)階，要么是先跳到第7級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第6級(jí)，然后一次邁2級(jí)臺(tái)階上去。

假設(shè)跳到第n級(jí)臺(tái)階的跳數(shù)我們定義為f(n)，可以得出公式：

f（10） = f（9）+f(8)f (9)  = f(8) + f(7)f (8)  = f(7) + f(6)...f(3) = f(2) + f(1)
即通用公式為: f(n) = f(n-1) + f(n-2)

那f(2) 或者 f(1) 等于多少呢？

?

當(dāng)只有2級(jí)臺(tái)階時(shí)，有兩種跳法，第一種是直接跳兩級(jí)，第二種是先跳一級(jí)，然后再跳一級(jí)。即f(2) = 2;

當(dāng)只有1級(jí)臺(tái)階時(shí)，只有一種跳法，即f（1）= 1；

public int getNum(int n) {??if(n?==?1){??????return?1;???}???if(n?==?2){??????return?2;???}??return?getNum(n-1)?+?getNum(n-2);}

大家通過(guò)看上面兩個(gè)例子心中是怎么想的呢

聰明的你們應(yīng)該早已經(jīng)發(fā)現(xiàn)其中的相似點(diǎn)了，沒(méi)錯(cuò)，它們的共同點(diǎn)就是都是有一些子問(wèn)題作為根基，然后這些子問(wèn)題會(huì)被重復(fù)的調(diào)用，計(jì)算

要計(jì)算最大的值，就必須先計(jì)算子問(wèn)題，要計(jì)算子問(wèn)題，就必須計(jì)算更子的問(wèn)題

仔細(xì)想一下這個(gè)計(jì)算過(guò)程，太多太多的重復(fù)計(jì)算了，每一個(gè)都被計(jì)算了不止一次，尤其是f(1)這種，所以這種是很低效的

既然存在了大量的重復(fù)計(jì)算，我們就可以先把計(jì)算好的答案保存下來(lái)，其實(shí)也就是一個(gè)備忘錄，等到下次需要的話(huà)，也就是先去備忘錄查詢(xún)一下，如果有，就直接取備忘錄的值就可以了，備忘錄沒(méi)有才開(kāi)始計(jì)算

類(lèi)似于我們平時(shí)系統(tǒng)中的緩存的效果

?

動(dòng)態(tài)規(guī)劃跟帶備忘錄的遞歸解法基本思想是一致的，都是減少重復(fù)計(jì)算，時(shí)間復(fù)雜度也都是差不多。

但是呢

?

帶備忘錄的遞歸，是從f(10)往f(1）方向延伸求解的，所以也稱(chēng)為自頂向下的解法。

動(dòng)態(tài)規(guī)劃從較小問(wèn)題的解，由交疊性質(zhì)，逐步?jīng)Q策出較大問(wèn)題的解，它是從f(1)往f(10）方向，往上推求解，所以稱(chēng)為自底向上的解法。

動(dòng)態(tài)規(guī)劃有幾個(gè)典型特征，最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程、邊界、重疊子問(wèn)題。

在青蛙跳階問(wèn)題中：

?

f(n-1)和f(n-2) 稱(chēng)為 f(n) 的最優(yōu)子結(jié)構(gòu)

f(n)= f（n-1）+f（n-2）就稱(chēng)為狀態(tài)轉(zhuǎn)移方程

f(1) = 1, f(2) = 2 就是邊界啦

比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重疊子問(wèn)題。

動(dòng)態(tài)規(guī)劃中的解題套路

通過(guò)上面說(shuō)了這么多了，我們知道動(dòng)態(tài)規(guī)劃的關(guān)鍵在于：存在重疊子問(wèn)題！

動(dòng)態(tài)規(guī)劃的本質(zhì)不在于是遞推或是遞歸，也不需要糾結(jié)是不是內(nèi)存換時(shí)間，本質(zhì)是解決的這些小問(wèn)題是否能夠被重復(fù)調(diào)用，這就是問(wèn)題是否可以用動(dòng)態(tài)規(guī)劃解決的要素

• 將原問(wèn)題分解為子問(wèn)題
• 確定狀態(tài)
• 確定一些初始狀態(tài)（邊界狀態(tài)）的值
  
• 寫(xiě)出狀態(tài)轉(zhuǎn)移方程

如果一個(gè)大問(wèn)題，可以把所有可能的答案都窮舉出來(lái)，窮舉出來(lái)之后會(huì)發(fā)現(xiàn)有很多重疊的子問(wèn)題，就可以考慮使用動(dòng)態(tài)規(guī)劃

比如一些求最值的場(chǎng)景，如最長(zhǎng)遞增子序列、最小編輯距離、背包問(wèn)題、湊零錢(qián)問(wèn)題等等，都是動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用場(chǎng)景。

?

動(dòng)態(tài)規(guī)劃的核心思想就是拆分子問(wèn)題，記住過(guò)往，減少重復(fù)計(jì)算。并且動(dòng)態(tài)規(guī)劃一般都是自底向上的，因此到這里，基于青蛙跳階問(wèn)題，我總結(jié)了一下我做動(dòng)態(tài)規(guī)劃的思路：

1、將原問(wèn)題分解為子問(wèn)題

把原問(wèn)題分解為若干個(gè)子問(wèn)題，子問(wèn)題和原問(wèn)題形式相同 或類(lèi)似，只不過(guò)規(guī)模變小了。

子問(wèn)題都解決，原問(wèn)題即解 決(數(shù)字三角形例）。l 子問(wèn)題的解一旦求出就會(huì)被保存，所以每個(gè)子問(wèn)題只需求 解一次。?

?

2、確定狀態(tài)

在用動(dòng)態(tài)規(guī)劃解題時(shí)，我們往往將和子問(wèn)題相 關(guān)的各個(gè)變量的一組取值，稱(chēng)之為一個(gè)“狀態(tài)”。

一個(gè)“狀態(tài)”對(duì)應(yīng)于一個(gè)或多個(gè)子問(wèn)題， 所謂某個(gè)“狀態(tài)”下的“值”，就是這個(gè)“狀 態(tài)”所對(duì)應(yīng)的子問(wèn)題的解。

所有“狀態(tài)”的集合，構(gòu)成問(wèn)題的“狀態(tài)空間”。“狀態(tài) 空間”的大小，與用動(dòng)態(tài)規(guī)劃解決問(wèn)題的時(shí)間復(fù)雜度直接相關(guān)。在數(shù)字三角形的例子里，一共有N×(N+1)/2個(gè)數(shù)字，所以這個(gè) 問(wèn)題的狀態(tài)空間里一共就有N×(N+1)/2個(gè)狀態(tài)。

整個(gè)問(wèn)題的時(shí)間復(fù)雜度是狀態(tài)數(shù)目乘以計(jì)算每個(gè)狀態(tài)所需時(shí)間。? ? ? ? ? ??

在數(shù)字三角形里每個(gè)“狀態(tài)”只需要經(jīng)過(guò)一次，且在每個(gè) 狀態(tài)上作計(jì)算所花的時(shí)間都是和N無(wú)關(guān)的常數(shù)。??

?

用動(dòng)態(tài)規(guī)劃解題，經(jīng)常碰到的情況是，K個(gè)整型變量能 構(gòu)成一個(gè)狀態(tài)（如數(shù)字三角形中的行號(hào)和列號(hào)這兩個(gè)變量 構(gòu)成“狀態(tài)”）。如果這K個(gè)整型變量的取值范圍分別是 N1, N2, ……Nk，那么，我們就可以用一個(gè)K維的數(shù)組 array[N1] [N2]……[Nk]來(lái)存儲(chǔ)各個(gè)狀態(tài)的“值”。

這個(gè) “值”未必就是一個(gè)整數(shù)或浮點(diǎn)數(shù)，可能是需要一個(gè)結(jié)構(gòu) 才能表示的，那么array就可以是一個(gè)結(jié)構(gòu)數(shù)組。一個(gè) “狀態(tài)”下的“值”通常會(huì)是一個(gè)或多個(gè)子問(wèn)題的解。

?

3、確定一些初始狀態(tài)（邊界狀態(tài)）的值

???????

以“數(shù)字三角形”為例，初始狀態(tài)就是底邊數(shù)字，值 就是底邊數(shù)字值。

4、確定狀態(tài)轉(zhuǎn)移方程

定義出什么是“狀態(tài)”，以及在該 “狀態(tài)”下的“值”后，就要 找出不同的狀態(tài)之間如何遷移――即如何從一個(gè)或多個(gè)“值”已知的 “狀態(tài)”，求出另一個(gè)“狀態(tài)”的“值”(“人人為我”遞推型)。

狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱(chēng)作“狀態(tài)轉(zhuǎn)移方程”。

?

能用動(dòng)規(guī)解決的問(wèn)題的特點(diǎn)

1) 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

如果問(wèn)題的最優(yōu)解所包含的 子問(wèn)題的解也是最優(yōu)的，我們就稱(chēng)該問(wèn)題具有最優(yōu)子結(jié) 構(gòu)性質(zhì)。

?

2) 無(wú)后效性。

當(dāng)前的若干個(gè)狀態(tài)值一旦確定，則此后過(guò)程 的演變就只和這若干個(gè)狀態(tài)的值有關(guān)，和之前是采取哪 種手段或經(jīng)過(guò)哪條路徑演變到當(dāng)前的這若干個(gè)狀態(tài)，沒(méi)有關(guān)系。