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

首先我們需要明確一點(diǎn)，什么是動(dòng)態(tài)規(guī)劃？

將一個(gè)問題分解為若干規(guī)模較小的子問題，通過求出子問題并保存子問題的解，然后再通過子問題來推導(dǎo)出原問題的解，這種算法就叫動(dòng)態(tài)規(guī)劃。

那怎么分辨動(dòng)態(tài)規(guī)劃算法與其他類似算法的區(qū)別呢？

你需要知道這三點(diǎn)：

1.最優(yōu)子結(jié)構(gòu)

2.狀態(tài)轉(zhuǎn)移方程

3.無后效性

這就是

動(dòng)態(tài)規(guī)劃的性質(zhì)

什么，你還是分不清？

請(qǐng)看Part 2。

Part 2 動(dòng)態(tài)規(guī)劃與常見算法的區(qū)別

動(dòng)態(tài)規(guī)劃vs遞推

動(dòng)態(tài)規(guī)劃的代碼與遞推算法是非常相似的，很多人會(huì)分不清，包括作者本人。

DP的一個(gè)重要特征就是需要保存狀態(tài)，而且需要保存之前的狀態(tài)，不一定是上一個(gè)狀態(tài)，DP的狀態(tài)可能需要使用很多次。

而遞推只需要保存上一個(gè)狀態(tài)，且一般只需要用到上一次的狀態(tài)。

動(dòng)態(tài)規(guī)劃vs分治

這兩個(gè)算法的共同點(diǎn)在于都需要分解為具備最優(yōu)子結(jié)構(gòu)的子問題，但分治一般分解為兩個(gè)子問題。

就算分解為多個(gè)子問題，那這些子問題也是并列關(guān)系。

DP就不一樣了，它的子問題關(guān)系更復(fù)雜，可以是重疊的、并列的或者互相包含的。

Part 3 線性DP和區(qū)間DP

讓我們先來看一道題：

有一個(gè)棋盤，共n行，m列，有一個(gè)卒子，從A(0,0)點(diǎn)出發(fā)，每次只能往右或往下移動(dòng)一步，求從A點(diǎn)到B(n,m)點(diǎn)的路徑條數(shù)。

解題思路：
定義狀態(tài)f(x,y),表示從起點(diǎn)走到(x,y)的路徑條數(shù)。則最終狀態(tài)為f(n,m),起始狀態(tài)為f(0,0).
動(dòng)態(tài)轉(zhuǎn)移方程為：f(x,y)=f(x-1,y)+f(x,y-1).

代碼如下：

int f[MAXN][MAXN]; int main(){ int n,m; cin>>n>>m; for(int i=0;i<=n;i++)f[i][0]=1; for(int i=0;i<=m;i++)f[0][i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=f[i-1][j]+f[i][j-1]; cout<<f[n][m]<<endl; }

由這道題的解題思路再推廣到這一類題的解題思路，總結(jié)得出：

在動(dòng)態(tài)規(guī)劃中，解題的關(guān)鍵通常是兩步： 第一步：定義好狀態(tài) 第二步：找出狀態(tài)轉(zhuǎn)移方程。（注意，找狀態(tài)轉(zhuǎn)移方程的時(shí)候要找出初始狀態(tài)）

線性DP例題 最長(zhǎng)上升子序列

設(shè)有由n個(gè)整數(shù)組成的數(shù)列，任意刪掉若干數(shù)后，剩下的部分稱為子序列。
如果子序列是從左到右依次遞增的，則稱為上升子序列。求該數(shù)列的最長(zhǎng)上升子序列的長(zhǎng)度。

線性DP例題 解題過程

定義狀態(tài)f(i)表示以i結(jié)束的最長(zhǎng)上升序列的長(zhǎng)度。
則狀態(tài)轉(zhuǎn)移方程為：
f(i)=max{f(j)+1) |j<i,a[j]<a[i] }
原問題的解則為max{f[i] | 0<=i<n }

這道題還可以拓展一下：如果要求輸出方案，如何處理？

由于方案有可能存在多種，請(qǐng)輸出最靠前的一種。

上題中我們已求出所有的數(shù)的f值，設(shè)其中最大的為f[i]，則a[i] 即為最長(zhǎng)上升子序列的尾數(shù)，

從a[i]處往左邊找，若a[j]<a[i]并且f[j]=f[i]-1，則a[j]必為序列的倒數(shù)第二個(gè)；

從j再往前找k，使得a[k]<a[j]并且f[k]=f[j]-1，即a[k]為序列的倒數(shù)第三個(gè)，以此類推，即可找到最長(zhǎng)上升序列中的所有數(shù)。

此題再次拓展，難度再次增加：如何求出最長(zhǎng)上升子序列有多少個(gè)？

在上一題基礎(chǔ)上，增加一個(gè)g數(shù)組，g[i]表示以a[i]結(jié)尾的最長(zhǎng)不下降子序列的個(gè)數(shù)。則g[i]=sum(g[j]) {j|j<i&&a[j]<=a[i]&&f[j]=f[i]-1}.
則ans=sum(g[i]) {此處的g[i]要滿足:f[i]最大}

區(qū)間DP例題 石子合并

設(shè)有n堆石子排成一排，其編號(hào)為1，2，3，…，n。每堆石子有一定的數(shù)量，例如： 13 7 8 16 21 4 18 現(xiàn)要將n堆石子歸并為一堆。歸并的過程為每次只能將相鄰的兩堆石子堆成一堆，這樣經(jīng)過n-1次歸并之后最后成為一堆。對(duì)于上面的7堆石子，可以有多種方法歸并成一堆。歸并的代價(jià)是這樣定義的：將兩堆石子歸并為一堆時(shí)，兩堆石子數(shù)量的和稱為歸并2堆石子的代價(jià)。如上圖中，將13和7歸并為一堆的代價(jià)為20。歸并的總代價(jià)指的是將沙子全部歸并為一堆沙子的代價(jià)的和。如上面的2種歸并方法中， 第1種的總代價(jià)為 20+24+25+44+69+87 = 267 第2種的總代價(jià)為 15+37+22+28+59+87 = 248 由此可見，不同歸并過程得到的總的歸并代價(jià)是不一樣的。 當(dāng)n堆石子的數(shù)量給出后，找出一種合理的歸并方法，使總的歸并代價(jià)為最小。

輸入
第1行：1個(gè)整數(shù)n(1<=n<=100)，表示石子的數(shù)量第
2行：n個(gè)用空格分開的整數(shù)，每個(gè)整數(shù)均小于10000，表示各堆石子的數(shù)量。
輸出
第1行：1個(gè)整數(shù)，表示最小的歸并代價(jià)
第2行：用括號(hào)表示的歸并順序。加括號(hào)的要求見樣例。如果只有1堆石子，輸出時(shí)不要加括號(hào)。
樣例輸入
3 13 7 8
樣例輸出
43 (13)((7)(8))

區(qū)間DP例題 石子合并

這是一個(gè)經(jīng)典的區(qū)間動(dòng)態(tài)規(guī)劃問題。
首先本題不能使用貪心。因?yàn)轭}中限定了必須是相鄰的兩堆才能合并。
從最后一次合并開始思考：
最后一次合并前，石子肯定只有兩堆，第一堆是原來的1到k堆，第二堆是原來的第k+1到第n堆。顯然，要使得總代價(jià)最小，必然是該兩堆式子之前的合并代價(jià)最小。
定義狀態(tài)f[i] [j]表示第i堆石子到第j堆石子的最小合并代價(jià)。則目標(biāo)狀態(tài)即為f[1][n]。
狀態(tài)轉(zhuǎn)移方程為：
f[i] [j]=min(f[i] [k]+f[k+1] [j])+sum(i,j)
初始狀態(tài)為f[i] [i]=0

注意狀態(tài)轉(zhuǎn)移方程
f[i] [j]=min(f[i] [k]+f[k+1] [j])+sum(i,j)
求f[i] [j]時(shí)，必須保證f[i] [k]、f[k+1] [j]已經(jīng)算出，但是k+1比i大。所以循環(huán)的順序應(yīng)當(dāng)是i遞減，j遞增。
或者換狀態(tài)。
以f[i] [len]表示從i開始的長(zhǎng)度為len的石子合并的最小代價(jià)。
則f[i] [len]=min(f[i] [k]+f[i+k] [len-k]+sum(I,i+len-1))

題目中需要輸出合并的方案。
所以求f[i] [j]的同時(shí)，要把k值也保存下來。
可以另開一個(gè)數(shù)組pos[i] [j]，將k值保存在pos[i] [j]中。輸出時(shí)，從pos[1] [n]開始遞歸輸出找k值，然后輸出答案。

Part 4 資源分配

工作分配問題

總公司擁有高效生產(chǎn)設(shè)備M臺(tái)，準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備，可以為國(guó)家提供一定的盈利。問：如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過總設(shè)備數(shù)M
數(shù)據(jù)文件格式為：第一行保存兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二個(gè)數(shù)是分公司數(shù)N。接下來是一個(gè)M*N的矩陣，表明了第i個(gè)公司分配j臺(tái)機(jī)器的盈利。

這種問題就是經(jīng)典的資源分配問題，定義狀態(tài)f[i] [j]表示前i個(gè)公司分配j臺(tái)機(jī)器的最大盈利。

則狀態(tài)轉(zhuǎn)移方程為:
f(i,j)=Max{f(i-1,k)+value(i,j-k)} (1<=i<=n,1<=j<=m,0<=k<=j )
初始值: f(0,0)=0
目標(biāo)狀態(tài)為f[n] [m]
時(shí)間復(fù)雜度O(N·M·M)

Part 5 多維DP

有時(shí)候我們會(huì)遇到一些狀態(tài)表示較為復(fù)雜的題，其維度達(dá)到或超過3維，這類題我們一般稱之為多維dp。
對(duì)于多維dp，要估算其時(shí)間復(fù)雜度和空間復(fù)雜度，保證其均不超過題目要求。否則，一定要努力降維，尋求優(yōu)化。

比如這一道非常經(jīng)典的真題：

NOIP2008 傳紙條

小淵和小軒是好朋友也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌甑脑掝}。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè)m行n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無法直接交談了。幸運(yùn)的是，他們可以通過傳紙條來進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。 還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時(shí)用0表示），可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大?，F(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。

輸入
第一行有2個(gè)用空格隔開的整數(shù)m和n，表示班里有m行n列（1≤m,n≤50） 接下來的m行是一個(gè)m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度。每行的n個(gè)整數(shù)之間用空格隔開。
輸出
共一行，包含一個(gè)整數(shù)，表示來回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值
樣例輸入
3 3
0 3 9
2 8 5
5 7 0
樣例輸出
34

題目要求找兩條來回的最大值路徑，也就相當(dāng)于找兩條從左上角同時(shí)出發(fā)，到達(dá)右下角的路徑，再簡(jiǎn)單點(diǎn)說，就是兩個(gè)人同時(shí)從左上角出發(fā)到右下角。

首先定義狀態(tài)為

f[s][i1][i2]

表示甲走到第i1行，乙走到第i2行，且甲乙各走了s步時(shí)，兩人所取得的數(shù)之和的最大值。

則狀態(tài)轉(zhuǎn)移方程為： f[s][i1][i2]=max(f[s-1][i1][i2],f[s-1][i1-1][i2-1],f[s-1][i1-1][i2],f[s-1][i1][i2-1])+num[s+2-i1]+num[i2][s+2-i2]; if(i1==i2)f[s][i1][i2]-=num[i1][s+2-i1]; 初始狀態(tài)f[0][1][1]=num[1][1] 目標(biāo)狀態(tài)f[m+n-2][m][n] m,n表示表格的行數(shù)、列數(shù)。

鏈接：https://www.dianjilingqu.com/684312.html