1. 前言
本節(jié)內(nèi)容是動(dòng)態(tài)規(guī)劃算法系列之一：動(dòng)態(tài)規(guī)劃的介紹，主要介紹了動(dòng)態(tài)規(guī)劃的定義按脚，什么樣的問(wèn)題適合用動(dòng)態(tài)規(guī)劃算法去求解，最后說(shuō)明動(dòng)態(tài)規(guī)劃算法在日常生活中的應(yīng)用場(chǎng)景。
2. 什么是動(dòng)態(tài)規(guī)劃败京？
動(dòng)態(tài)規(guī)劃（Dynamic Programming）在數(shù)學(xué)上屬于運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程 （decision process）最優(yōu)化的數(shù)學(xué)方法梦染，同時(shí)也是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中一種常見(jiàn)的算法思想赡麦。
動(dòng)態(tài)規(guī)劃算法與我們前面提及的分治算法相似朴皆，都是通過(guò)組合子問(wèn)題的解來(lái)求解原問(wèn)題的解。但是兩者之間也有很大區(qū)別：分治法將問(wèn)題劃分為互不相交的子問(wèn)題泛粹，遞歸的求解子問(wèn)題遂铡，再將他們的解組合起來(lái)求解原問(wèn)題的解；與之相反晶姊，動(dòng)態(tài)規(guī)劃應(yīng)用于子問(wèn)題相互重疊的情況扒接，在這種情況下，分治法還是會(huì)做很多重復(fù)的不必要的工作帽借，他會(huì)反復(fù)求解那些公共的子問(wèn)題珠增，而動(dòng)態(tài)規(guī)劃算法則對(duì)相同的每個(gè)子問(wèn)題只會(huì)求解一次，將其結(jié)果保存起來(lái)砍艾，避免一些不必要的計(jì)算工作蒂教。
Tips: 這里說(shuō)到的動(dòng)態(tài)規(guī)劃應(yīng)用于子問(wèn)題相互重疊的情況，是指原問(wèn)題不同的子問(wèn)題之間具有相同的更小的子子問(wèn)題脆荷，他們的求解過(guò)程和結(jié)果完全一樣凝垛。
動(dòng)態(tài)規(guī)劃算法更多的時(shí)候是用來(lái)求解一些最優(yōu)化問(wèn)題，這些問(wèn)題有很多可行解蜓谋，每個(gè)解都有一個(gè)值梦皮，利用動(dòng)態(tài)規(guī)劃算法是希望找到具有最優(yōu)值的解。接下來(lái)桃焕，就讓我們具體看看動(dòng)態(tài)規(guī)劃算法的求解思路及相關(guān)應(yīng)用場(chǎng)景剑肯。
3. 動(dòng)態(tài)規(guī)劃算法求解分析
3.1 適用問(wèn)題
首先，在利用動(dòng)態(tài)規(guī)劃算法之前观堂，我們需要清楚哪些問(wèn)題適合用動(dòng)態(tài)規(guī)劃算法求解让网。一般而言，能夠利用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題都會(huì)具備以下兩點(diǎn)性質(zhì)：
- 最優(yōu)子結(jié)構(gòu)： 利用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的第一步就是需要刻畫(huà)問(wèn)題最優(yōu)解的結(jié)構(gòu)师痕，并且如果一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解溃睹，則此問(wèn)題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。因此胰坟，判斷某個(gè)問(wèn)題是否適合用動(dòng)態(tài)規(guī)劃算法因篇，需要判斷該問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)。
Tips: 最優(yōu)子結(jié)構(gòu)的定義主要是在于當(dāng)前問(wèn)題的最優(yōu)解可以從子問(wèn)題的最優(yōu)解得出笔横，當(dāng)子問(wèn)題滿足最優(yōu)解之后竞滓，才可以通過(guò)子問(wèn)題的最優(yōu)解獲得原問(wèn)題的最優(yōu)解。
- 重疊子問(wèn)題： 適合用動(dòng)態(tài)規(guī)劃算法去求解的最優(yōu)化問(wèn)題應(yīng)該具備的第二個(gè)性質(zhì)是問(wèn)題的子問(wèn)題空間必須足夠” 小 “吹缔，也就是說(shuō)原問(wèn)題遞歸求解時(shí)會(huì)重復(fù)相同的子問(wèn)題虽界，而不是一直生成新的子問(wèn)題。如果原問(wèn)題的遞歸算法反復(fù)求解相同的子問(wèn)題涛菠，我們就稱(chēng)該最優(yōu)化問(wèn)題具有重疊子問(wèn)題。
Tips: 在這里，我們需要注意是俗冻，與適用動(dòng)態(tài)規(guī)劃算法去求解的問(wèn)題具備重疊子問(wèn)題性質(zhì)相反礁叔，前面我們介紹的分治算法遞歸解決問(wèn)題時(shí)，問(wèn)題的子問(wèn)題都是互不影響迄薄，相互獨(dú)立的琅关，這個(gè)也是我們?cè)谶x用動(dòng)態(tài)規(guī)劃算法還是分治法解決問(wèn)題時(shí)的一個(gè)判斷條件。
3.2 算法步驟
在明確什么樣的問(wèn)題適合用動(dòng)態(tài)規(guī)劃算法去求解時(shí)讥蔽，我們需要掌握動(dòng)態(tài)規(guī)劃算法的求解步驟：
步驟 1： 刻畫(huà)一個(gè)最優(yōu)解的結(jié)構(gòu)特征
適合用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題需要滿足最優(yōu)子結(jié)構(gòu)的特征涣易，所以在應(yīng)用動(dòng)態(tài)規(guī)劃算法時(shí)的第一步就是刻畫(huà)問(wèn)題最優(yōu)解的結(jié)構(gòu)，一般都是用一些數(shù)學(xué)方法去描述求解問(wèn)題冶伞，用數(shù)學(xué)公式表明最優(yōu)解的結(jié)構(gòu)特征新症。
步驟 2： 遞歸的定義最優(yōu)解的值
當(dāng)應(yīng)用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題時(shí)，一般我們會(huì)遞歸的求解相同的子問(wèn)題响禽，這個(gè)時(shí)候徒爹，我們就需要去遞歸的定義最優(yōu)解的值，通常也是先用數(shù)學(xué)公式去遞歸定義芋类。
步驟 3： 計(jì)算最優(yōu)解的值
當(dāng)我們可以清楚的刻畫(huà)一個(gè)最優(yōu)解的結(jié)構(gòu)特征及可以遞歸的定義出最優(yōu)解的值之和隆嗅，一般我們就可以采用自底向上的方法逐步去計(jì)算每一個(gè)最優(yōu)解的值，大問(wèn)題的最優(yōu)解的值依賴于小問(wèn)題的最優(yōu)解的值侯繁，這個(gè)是動(dòng)態(tài)規(guī)劃算法的核心思想胖喳。
步驟 4: 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
前面的步驟 1,2,3 是動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的基礎(chǔ)，如果我們僅僅需要一個(gè)最優(yōu)解的值贮竟，而不是需要了解最優(yōu)解本身丽焊，我們可以不用去執(zhí)行步驟 4；如果我們需要了解最優(yōu)解的具體情況坝锰，我們就需要在執(zhí)行步驟 3 的時(shí)候維護(hù)一些額外的信息粹懒，以便用來(lái)構(gòu)造出一個(gè)最優(yōu)解。
4. 動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景
在日常的生活學(xué)習(xí)中顷级，遞動(dòng)態(tài)規(guī)劃算法一般可以用來(lái)解決很多實(shí)際問(wèn)題≠旃裕現(xiàn)在，我們就來(lái)看看動(dòng)態(tài)規(guī)劃算法具體有哪些應(yīng)用場(chǎng)景弓颈。
動(dòng)態(tài)規(guī)劃示例問(wèn)題：爬樓梯
假設(shè)你現(xiàn)在正在爬樓梯帽芽，一共需要經(jīng)過(guò) n 階樓梯你才可以到達(dá)樓頂。每次你可以爬 樓梯的 1 或 2 個(gè)臺(tái)階翔冀。請(qǐng)問(wèn)一共有多少種不同的方法可以爬到樓頂导街？
現(xiàn)在，讓我們按照動(dòng)態(tài)規(guī)劃算法的求解步驟我們來(lái)分析一下這個(gè)問(wèn)題：
步驟 1： 刻畫(huà)爬樓梯問(wèn)題一個(gè)最優(yōu)解的結(jié)構(gòu)特征
情況 1：輸入 n=1纤子；輸出為 1
解釋 1：有一種情況可以爬上樓頂搬瑰， 爬 1 步款票，記為 1
情況 2：輸入 n=2；輸出為 2
解釋 2：有兩種情況可以爬上樓頂泽论，分別為連續(xù)兩次爬一階樓梯和一次爬兩階樓梯艾少，記為 1+1，2
情況 3：輸入 n=3翼悴；輸出為 3
解釋 3：有三種情況可以爬上樓頂缚够，如情況 1 和 2 描述一樣，記為 1+1+1,2+1,1+2
通過(guò)分析可以知道鹦赎，爬樓梯問(wèn)題主要在于我們可以一次爬兩步或者一步谍椅，所以到達(dá)最后一階樓梯 n 時(shí)，我們可以從第 n-2 階樓梯爬兩步或者第 n-1 樓梯爬一步完成古话。
當(dāng)我們需要知道最多有多少種方法可以爬上 n 階的樓梯時(shí)雏吭，我們需要分別知道爬上第 n-2 階樓梯最多有多少種方法，爬上第 n-1 階樓梯最多有多少種方法煞额，然后爬上第 n 階樓梯的最多方法數(shù)量等于爬上第 n-1 階樓梯最多的方法數(shù)量加上爬上第 n-2 階樓梯最多的方法數(shù)量思恐。
Tips: 在這里，我們可以發(fā)現(xiàn)爬樓梯問(wèn)題滿足第 3 節(jié)我們定義的動(dòng)態(tài)規(guī)劃算法需要具備的兩種性質(zhì)膊毁，其中的最優(yōu)子結(jié)構(gòu)就是：爬上 n 階樓梯的最多方法數(shù)包含爬上第 n-1 樓梯和第 n-2 階樓梯的最多方法數(shù)胀莹；重疊子問(wèn)題：需要反復(fù)的計(jì)算爬各階樓梯的最多方法數(shù)。
步驟 2： 遞歸的定義爬 n 階樓梯最多的方法數(shù)
- 上 1 階臺(tái)階：有 1 鐘方法婚温；
- 上 2 階臺(tái)階：有 1+1 和 2 兩種方法描焰；
- 上 3 階臺(tái)階：到達(dá)第 3 階的方法總數(shù)是到達(dá)第 1 階和第 2 階方法的總和；
- 上 n 階臺(tái)階：到達(dá)第 n 階的方法總數(shù)就是到第 (n-1) 階和第 (n-2) 階的方法數(shù)之和栅螟。
綜上所述荆秦，我們可以知道爬 n 階樓梯的狀態(tài)轉(zhuǎn)移方程可以定義為：goStep (n) = goStep (n-1)+goStep (n-2)。動(dòng)態(tài)規(guī)劃算法最重要的就是去定義這個(gè)狀態(tài)轉(zhuǎn)移方程力图，通過(guò)這個(gè)狀態(tài)轉(zhuǎn)移方程我們就可以很清楚的去計(jì)算步绸。
步驟 3： 計(jì)算爬 n 階樓梯最多方法數(shù)的值
| 樓梯階數(shù) n | 爬 n 階樓梯最多的方法數(shù) |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | goStep(1)+goStep(2)=1+2=3 |
| 4 | goStep(2)+goStep(3)=2+3=5 |
| 5 | goStep(3)+goStep(4)=3+5=8 |
| 6 | goStep(4)+goStep(5)=5+8=13 |
| 7 | goStep(5)+goStep(6)=8+13=21 |
| 8 | goStep(6)+goStep(7)=13+21=36 |
| 9 | goStep(7)+goStep(8)=21+36=57 |
步驟 4： 利用計(jì)算出的信息構(gòu)爬 n 階樓梯每次走幾步的方法
其實(shí)在爬樓梯這個(gè)問(wèn)題中，我們并不需要統(tǒng)計(jì)每次的具體爬樓梯方法吃媒，如果需要統(tǒng)計(jì)每次具體走法時(shí)瓤介，需要在計(jì)算的時(shí)候記錄之前的每一步走法，把信息全部記錄保留下來(lái)即可赘那。
我們可以很明顯的發(fā)現(xiàn)刑桑，動(dòng)態(tài)規(guī)劃算法很多時(shí)候都是應(yīng)用于求解一些最優(yōu)化問(wèn)題（最大，最小募舟，最多祠斧，最少），這類(lèi)問(wèn)題在現(xiàn)實(shí)生活或者學(xué)習(xí)科研中經(jīng)常會(huì)遇到拱礁，這是一種解決問(wèn)題的思路與方法琢锋，希望大家可以好好思考辕漂。
5. 小結(jié)
本節(jié)主要介紹了動(dòng)態(tài)規(guī)劃算法的定義及基本概念，在學(xué)完本節(jié)課程之后吩蔑，需要明白什么樣的問(wèn)題適合利用動(dòng)態(tài)規(guī)劃求解钮热，如何自己去設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，以及我們?nèi)粘Ｉ钪心男?yīng)用場(chǎng)景適合用動(dòng)態(tài)規(guī)劃思想解決問(wèn)題烛芬。
