1.簡介

動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃也是學(xué)習(xí)算法的同學(xué)最為頭疼的一個(gè)重要算法，其類型寬泛讓人無從下手，又極其的燒腦很難理解，事實(shí)上，動(dòng)態(tài)規(guī)劃是算法學(xué)習(xí)者的一個(gè)重要的門檻，也是一個(gè)瓶頸，掌握方法很重要，本節(jié)雖然不提供任何的具體代碼，但希望簡介以及介紹曲線的方式讓讀者能夠更好的掌握。

2.思想

動(dòng)態(tài)規(guī)劃的基本思想是：問題的最優(yōu)解如果可以由子問題的最優(yōu)解推導(dǎo)得到，則可以先求解子問題的最優(yōu)解，在構(gòu)造原問題的最優(yōu)解；若子問題有較多的重復(fù)出現(xiàn)，則可以自底向上從最終子問題向原問題逐步求解。

比如說著名的斐波那契定理a[i]=a[i-1]+a[i-2]，就是一個(gè)特別好的理解方式，為什么直接寫公式的算法（自底向上，從1開始遞增）效率就是比遞歸（自頂向下，從n開始向下）的要好？

讓我們來熟悉一下動(dòng)態(tài)規(guī)劃的特點(diǎn)：

a) 把原始問題劃分成一系列子問題；

b) 求解每個(gè)子問題僅一次，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)直接存取，不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間

c) 自底向上地計(jì)算。

d) 整體問題最優(yōu)解取決于子問題的最優(yōu)解（狀態(tài)轉(zhuǎn)移方程）（將子問題稱為狀態(tài)，最終狀態(tài)的求解歸結(jié)為其他狀態(tài)的求解）

很簡單，因?yàn)檫f歸的方式return f(n-1)+f(n-2)會(huì)產(chǎn)生一些重復(fù)計(jì)算，當(dāng)計(jì)算f(5)+f(4)中，f(5)其實(shí)又包含了一次f(4)，而動(dòng)態(tài)規(guī)劃的出現(xiàn)，就是為了減少這樣的重復(fù)計(jì)算，通過確認(rèn)一個(gè)個(gè)的狀態(tài)以及到達(dá)下一個(gè)狀態(tài)的【狀態(tài)轉(zhuǎn)移方程】，來表現(xiàn)，一般而言，我們使用數(shù)學(xué)語言直接表示【狀態(tài)轉(zhuǎn)移方程】。

3. 分類

動(dòng)態(tài)規(guī)劃可以分為如下四大類，可以依次進(jìn)行學(xué)習(xí)：

線性動(dòng)規(guī)，區(qū)域動(dòng)規(guī)，樹形動(dòng)規(guī)，背包動(dòng)規(guī)。

4. 學(xué)習(xí)方法

一切的開始，都必須要勤記筆記，在最初的學(xué)習(xí)中，比如最大不下降子序列這題目，我們可以更具題意將題目要求，總結(jié)題目意思，發(fā)現(xiàn)是否選取這個(gè)序列數(shù)是一個(gè)狀態(tài)，這個(gè)狀態(tài)分為兩種情況：選取，不選取，我們可以在草稿紙上面講每一個(gè)狀態(tài)利用一個(gè)二叉樹畫出來，然后推到出正確的方案，這是第一步，接著我們講二叉樹中的每一個(gè)數(shù)據(jù)提出，嘗試著利用動(dòng)態(tài)規(guī)劃的思維，將這課樹的狀態(tài)轉(zhuǎn)移方程提出，最后根據(jù)這個(gè)狀態(tài)轉(zhuǎn)移方程，寫出最終的答案。

在熟悉相關(guān)類型的題目達(dá)到一定的程度的時(shí)候，自然得心應(yīng)手。

5. 相關(guān)例題

可以直接從dotcpp網(wǎng)站標(biāo)簽中搜索動(dòng)態(tài)規(guī)劃即可，動(dòng)態(tài)規(guī)劃擁有海量的題目，非常適合深入理解和練習(xí)。