動(dòng)態(tài)規(guī)劃（Dynamic Programming，簡稱DP），是大家都覺得比較難以掌握的算法。為了應(yīng)付面試，我們經(jīng)常會(huì)背誦一下DP問題的源碼，其實(shí)，只要理解了思想，掌握基本的模型，然后再來點(diǎn)寫代碼的套路，動(dòng)態(tài)規(guī)劃并沒有那么難。

先來回顧一下題型目錄。

動(dòng)態(tài)規(guī)劃基本題型總結(jié)提綱目錄

1.硬幣找零，路徑規(guī)劃

2.字符串相似度/編輯距離（edit distance）

3.最長公共子序列(Longest Common Subsequence,lcs)

4.最長遞增子序列（Longest Increasing Subsequence,lis）

5.最大子序列積

6.矩陣鏈乘法

7.0-1背包問題

8.有代價(jià)的最短路徑

9.瓷磚覆蓋（狀態(tài)壓縮DP）

10.工作量劃分

11.三路取蘋果

上篇文章講到第五個(gè)題型，最大子序列積，這篇從第六個(gè)題型開始。

6.矩陣鏈乘法

先看矩陣乘法

從定義可以看出：只有當(dāng)矩陣A的列數(shù)與矩陣B的行數(shù)相等時(shí)A×B才有意義。一個(gè)m×r的矩陣A左乘一個(gè)r×n的矩陣B，會(huì)得到一個(gè)m×n的矩陣C。在計(jì)算機(jī)中，一個(gè)矩陣說穿了就是一個(gè)二維數(shù)組。一個(gè)m行r列的矩陣可以乘以一個(gè)r行n列的矩陣，得到的結(jié)果是一個(gè)m行n列的矩陣，其中的第i行第j列位置上的數(shù)等于前一個(gè)矩陣第i行上的r個(gè)數(shù)與后一個(gè)矩陣第j列上的r個(gè)數(shù)對(duì)應(yīng)相乘后所有r個(gè)乘積的和。

所謂矩陣鏈乘法是指當(dāng)一些矩陣相乘時(shí)，如何加括號(hào)來改變乘法順序從而來降低乘法次數(shù)。例如有三個(gè)矩陣連乘：A1*A2*A3，其維數(shù)分別為：10*100，100*5，5*50.如果按照（（A1*A2）A3）來計(jì)算的話，求（A1*A2）要10*100*5=5000次乘法，再乘以A3需要10*5*50=2500次乘法，因此總共需要7500次乘法。如果按照（A1（A2*A3））來計(jì)算的話，求（A2*A3）要100*5*50=25000次乘法，再乘以A1需要10*100*50=50000次乘法，因此總共需要75000次乘法。可見，按不同的順序計(jì)算，代價(jià)相差很大。

比如對(duì)于這個(gè)M?M?M?的矩陣鏈，

我們可以先計(jì)算M?M?然后結(jié)果乘以M?，也可以M?M?先算，然后乘以M?，為了表達(dá)方便，可以用括號(hào)表示計(jì)算順序。 矩陣鏈M?M?M?有兩種計(jì)算順序：((M?M?)M?)和(M?(M?M?))。 那么不同計(jì)算順序有什么區(qū)別？ 對(duì)于((M?M?)M?):

對(duì)于(M?(M?M?))：

我們要做的就是找到讓乘法運(yùn)算最少的計(jì)算順序，換言之就是找一種加括號(hào)方式，使得最后乘法運(yùn)算最少。

矩陣鏈乘法問題可以表述如下：給定n個(gè)矩陣構(gòu)成的一個(gè)鏈（A1*A2*A3……*An），其中i=1,2,……n,矩陣Ai的維數(shù)為p(i-1)*p(i),對(duì)于乘積A1*A2*A3……*An以一種最小化標(biāo)量乘法次數(shù)的方式進(jìn)行加括號(hào)。

這個(gè)問題太難理解了。

為了代入問題，先來樸素算法，這個(gè)總能看懂吧。

void mult(int a[MAXN][MAXN],int b[MAXN][MAXN],int c[MAXN][MAXN],int p,int q,int r) { int i,j,k; //先對(duì)c進(jìn)行初始化 for(i=0;i<p;i++) { for(j=0;j<r;j++) { c[i][j] = 0; } } //計(jì)算矩陣乘法 for(i=0;i<p;i++) { for(j=0;j<r;j++) { for(k=0;k<q;k++) { c[i][j] += a[i][k] * b[k][j]; } } } }

解決這個(gè)問題，我們可以用窮舉法，但是n很大時(shí)，這不是個(gè)好方法，其時(shí)間復(fù)雜度為指數(shù)形式。拿上面的例子來說，加括號(hào)后把矩陣鏈分成了兩部分，計(jì)算代價(jià)為兩者代價(jià)的和。因此假設(shè)這種方法的代價(jià)最少，則兩個(gè)部分的代價(jià)也是最小的，如果不是最小的，那么這種方法就不是最優(yōu)的，因此矩陣鏈乘法具有最優(yōu)子結(jié)構(gòu)。因此我們可以利用子問題的最優(yōu)解來構(gòu)造原問題的一個(gè)最優(yōu)解。所以，可以把問題分割為兩個(gè)子問題（A1*A2*A3……*Ak和A(k+1)*A(k+2)*A(k+3)……*An）,需找子問題的最優(yōu)解，然后合并這些問題的最優(yōu)解。從下面的程序可以看出，其時(shí)間復(fù)雜度為n*n*n.

題目分析：

遞推關(guān)系：

設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]。

當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n

當(dāng)i<j時(shí)，若A[i:j]的最優(yōu)次序在Ak和Ak+1之間斷開，i<=k<j,則：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在計(jì)算是并不知道斷開點(diǎn)k的位置，所以k還未定。不過k的位置只有j-i個(gè)可能。因此，k是這j-i個(gè)位置使計(jì)算量達(dá)到最小的那個(gè)位置。

綜上，有遞推關(guān)系如下：

構(gòu)造最優(yōu)解：

若將對(duì)應(yīng)m[i][j]的斷開位置k記為s[i][j]，在計(jì)算出最優(yōu)值m[i][j]后，可遞歸地由s[i][j]構(gòu)造出相應(yīng)的最優(yōu)解。s[i][j]中的數(shù)表明，計(jì)算矩陣鏈A[i:j]的最佳方式應(yīng)在矩陣Ak和Ak+1之間斷開，即最優(yōu)的加括號(hào)方式應(yīng)為(A[i:k])(A[k+1:j)。因此，從s[1][n]記錄的信息可知計(jì)算A[1:n]的最優(yōu)加括號(hào)方式為(A[1:s[1][n]])(A[s[1][n]+1:n])，進(jìn)一步遞推，A[1:s[1][n]]的最優(yōu)加括號(hào)方式為(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]])。同理可以確定A[s[1][n]+1:n]的最優(yōu)加括號(hào)方式在s[s[1][n]+1][n]處斷開…照此遞推下去，最終可以確定A[1:n]的最優(yōu)完全加括號(hào)方式，及構(gòu)造出問題的一個(gè)最優(yōu)解。

動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn)

用動(dòng)態(tài)規(guī)劃迭代方式解決此問題，可依據(jù)其遞歸式自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題的答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只需簡單檢查一下，從而避免了大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。

代碼如下：

//3d1-2 矩陣連乘 動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn) //A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25 //p[0-6]={30,35,15,5,10,20,25} #include "stdafx.h" #include <iostream> using namespace std; const int L = 7; int MatrixChain(int n,int **m,int **s,int *p); void Traceback(int i,int j,int **s);//構(gòu)造最優(yōu)解 int main() { int p[L]={30,35,15,5,10,20,25}; int **s = new int *[L]; int **m = new int *[L]; for(int i=0;i<L;i++) { s[i] = new int[L]; m[i] = new int[L]; } cout<<"矩陣的最少計(jì)算次數(shù)為："<<MatrixChain(6,m,s,p)<<endl; cout<<"矩陣最優(yōu)計(jì)算次序?yàn)?#xff1a;"<<endl; Traceback(1,6,s); return 0; } int MatrixChain(int n,int **m,int **s,int *p) { for(int i=1; i<=n; i++) { m[i][i] = 0; } for(int r=2; r<=n; r++) //r為當(dāng)前計(jì)算的鏈長（子問題規(guī)模） { for(int i=1; i<=n-r+1; i++)//n-r+1為最后一個(gè)r鏈的前邊界 { int j = i+r-1;//計(jì)算前邊界為r，鏈長為r的鏈的后邊界 m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//將鏈ij劃分為A(i) * ( A[i+1:j] ) s[i][j] = i; for(int k=i+1; k<j; k++) { //將鏈ij劃分為( A[i:k] )* (A[k+1:j]) int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t<m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } return m[1][L-1]; } void Traceback(int i,int j,int **s) { if(i==j) return; Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); cout<<"Multiply A"<<i<<","<<s[i][j]; cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl; }

7.0-1背包問題

題目描述：

有n個(gè)物品，它們有各自的體積和價(jià)值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

為方便講解和理解，下面講述的例子均先用具體的數(shù)字代入，即：eg：number＝4，capacity＝8

有n個(gè)物品，每個(gè)物品有兩個(gè)屬性：一個(gè)是體積,一個(gè)是價(jià)值 ，可以表示為：(w1,v1),(w1,v1),…,(w1,vn) {(w_1,v_1 ),(w_1,v_1 ),…,(w_1,v_n )} )。同時(shí)我們還有一背包，背包的容量用W表示。現(xiàn)在我們將物品放入背包，放入的物品體積的總和不得超過背包的體積。

問:這個(gè)背包能裝下的最大價(jià)值。

題目分析：

　　①、將原問題分解為子問題（子問題和原問題形式相同，且子問題解求出就會(huì)被保存）；

　　②、確定狀態(tài)：01背包中一個(gè)狀態(tài)就是NN個(gè)物體中第ii個(gè)是否放入體積為VV背包中；

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

　　④、確定狀態(tài)轉(zhuǎn)移方程，如何從一個(gè)或多個(gè)已知狀態(tài)求出另一個(gè)未知狀態(tài)的值。（遞推型）

思路：

①、確認(rèn)子問題和狀態(tài)

　　01背包問題需要求解的就是，為了體積V的背包中物體總價(jià)值最大化，NN件物品中第ii件應(yīng)該放入背包中嗎？（其中每個(gè)物品最多只能放一件）

　　為此，我們定義一個(gè)二維數(shù)組，其中每個(gè)元素代表一個(gè)狀態(tài)，即前ii個(gè)物體中若干個(gè)放入體積為VV背包中最大價(jià)值。數(shù)組為：f[N][V]f[N][V]，其中fijfij表示前ii件中若干個(gè)物品放入體積為jj的背包中的最大價(jià)值。

　　②、初始狀態(tài)

　　初始狀態(tài)為f[0][0?V]f[0][0?V]和f[0?N][0]f[0?N][0]都為0，前者表示前0個(gè)物品（也就是空物品）無論裝入多大的包中總價(jià)值都為0，后者表示體積為0的背包啥價(jià)值的物品都裝不進(jìn)去。

　　③、轉(zhuǎn)移函數(shù)

if (背包體積j小于物品i的體積)f[i][j] = f[i-1][j] //背包裝不下第i個(gè)物體，目前只能靠前i-1個(gè)物體裝包 elsef[i][j] = max(f[i-1][j], f[i-1][j-Vi] + Wi)

　　最后一句的意思就是根據(jù)“為了體積V的背包中物體總價(jià)值最大化，NN件物品中第ii件應(yīng)該放入背包中嗎？”轉(zhuǎn)化而來的。ViVi表示第ii件物體的體積，WiWi表示第ii件物品的價(jià)值。這樣f[i-1][j]代表的就是不將這件物品放入背包，而f[i-1][j-Vi] + Wi則是代表將第i件放入背包之后的總價(jià)值，比較兩者的價(jià)值，得出最大的價(jià)值存入現(xiàn)在的背包之中。

01背包問題其實(shí)就可以化簡為涂寫下面的表格，其中每個(gè)數(shù)對(duì)應(yīng)數(shù)組nArr中每個(gè)元素，初始化部分為0，然后從左上角按行求解，一直求解到右下角獲取最終解nArr[5][12]。

代碼如下：

#include<iostream> using namespace std;int main() {int nArr[6][13] = {{0}};int nCost[6] = {0 , 2 , 5 , 3 , 10 , 4}; //花費(fèi)int nVol[6] = {0 , 1 , 3 , 2 , 6 , 2}; //物體體積int bagV = 12;for( int i = 1; i< sizeof(nCost)/sizeof(int); i++){for( int j = 1; j<=bagV; j++){if(j<nVol[i])nArr[i][j] = nArr[i-1][j];elsenArr[i][j] = max(nArr[i-1][j] , nArr[i-1][j-nVol[i]] + nCost[i]); cout<<nArr[i][j]<<' ';} cout<<endl;}cout<<nArr[5][12]<<endl;return 0; }

再來看另外一個(gè)課件上的解釋：

背包問題是動(dòng)態(tài)規(guī)劃里面比較出名的題型，其變種題目很多，由于篇幅有限就不一一展開了，下面只列出背包問題的題型目錄。

一、01背包問題

這是最基本的背包問題，每個(gè)物品最多只能放一次。

二、完全背包問題

第二個(gè)基本的背包問題模型，每種物品可以放無限多次。

三、 多重背包問題

每種物品有一個(gè)固定的次數(shù)上限。

四、 混合三種背包問題

將前面三種簡單的問題疊加成較復(fù)雜的問題。

五、二維費(fèi)用的背包問題

一個(gè)簡單的常見擴(kuò)展。

六、分組的背包問題

一種題目類型，也是一個(gè)有用的模型。后兩節(jié)的基礎(chǔ)。

七、 有依賴的背包問題

另一種給物品的選取加上限制的方法。

八 、泛化物品

九、 背包問題問法的變化

試圖觸類旁通、舉一反三。

8.有代價(jià)的最短路徑

從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。

現(xiàn)在只討論Dijkstra算法。

1。指定一個(gè)節(jié)點(diǎn)，例如我們要計(jì)算 'A' 到其他節(jié)點(diǎn)的最短路徑

2.引入兩個(gè)集合（S、U），S集合包含已求出的最短路徑的點(diǎn)（以及相應(yīng)的最短長度），U集合包含未求出最短路徑的點(diǎn)（以及A到該點(diǎn)的路徑，注意 如上圖所示，A->C由于沒有直接相連 初始時(shí)為∞）

3.初始化兩個(gè)集合，S集合初始時(shí) 只有當(dāng)前要計(jì)算的節(jié)點(diǎn)，A->A = 0，

U集合初始時(shí)為 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞，敲黑板！！！接下來要進(jìn)行核心兩步驟了

4.從U集合中找出路徑最短的點(diǎn)，加入S集合，例如 A->D = 2

5.更新U集合路徑，if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 則更新U

循環(huán)執(zhí)行 4、5 兩步驟，直至遍歷結(jié)束，得到A 到其他節(jié)點(diǎn)的最短路徑

比如現(xiàn)在求A到E的最短加權(quán)路徑，路徑上的數(shù)值為權(quán)重。

1.選定A節(jié)點(diǎn)并初始化，如上述步驟3所示

2.執(zhí)行上述 4、5兩步驟，找出U集合中路徑最短的節(jié)點(diǎn)D 加入S集合，并根據(jù)條件if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' )來更新U集合。

3.這時(shí)候A->B, A->C都為3，沒關(guān)系。其實(shí)這時(shí)候他倆都是最短距離，如果從算法邏輯來講的話，會(huì)先取到B點(diǎn)。而這個(gè)時(shí)候 if 條件變成了if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' )，如圖所示這時(shí)候A->B距離 其實(shí)為A->D->B

4.思路就是這樣，往后就是大同小異了

5.算法結(jié)束

大致步驟：

清除所有點(diǎn)的標(biāo)號(hào) 全部d[i] = INF 然后將圖信息權(quán)值復(fù)制到d中 循環(huán)n次{在所有為標(biāo)號(hào)的結(jié)點(diǎn)中，選出d值最小的結(jié)點(diǎn)x給x標(biāo)記對(duì)于從x出發(fā)的所有邊(x,y)，更新d[y] = min{d[y],d[y]+w(x,y)}

代碼如下：

#include <bits/stdc++.h> using namespace std; const int maxn = 500; const int INF = 0x3f3f3f3f; int n,m,dis[maxn],Map[maxn][maxn],v[maxn]; void dijkstra(int u) {memset(v,0,sizeof v);memset(dis,INF,sizeof dis);v[u] = 1;for(int i = 1; i <= n; i++)dis[i] = min(dis[i],Map[u][i]);for(int i = 1; i <= n; i++){int x,m = INF;for(int y = 1; y <= n; y++)if(!v[y] && dis[y] <= m)m = dis[x = y];v[x] = 1;for(int y = 1; y <= n; y++)dis[y] = min(dis[y],dis[x]+Map[x][y] );} } int main() {int a,u,v,w;scanf("%d%d%d",&n,&m,&a);memset(Map, INF, sizeof Map);for(int i = 0; i < m; i++){scanf("%d%d%d",&u,&v,&w);Map[u][v] = w;Map[v][u] = w; //該圖為無向圖，若為有向圖則需要少建立一個(gè)邊信息}for(int i = 1; i <= n; i++)Map[i][i] = 0;dijkstra(a);for(int i = 1; i <= n; i++)cout<<dis[i]<<" ";return 0; }

動(dòng)態(tài)規(guī)劃還有最后幾個(gè)題型，下篇會(huì)都說完。再后面我會(huì)分享貪心算法、回溯算法、分治算法，排序算法。歡迎一起學(xué)習(xí)。

總結(jié)

以上是生活随笔為你收集整理的c++矩阵连乘的动态规划算法并输出_算法面试必修课，动态规划基础题型归纳（三）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。