動態(tài)規(guī)劃入門

動態(tài)規(guī)劃入門2021/5/91三角形的行數(shù)大于1小于等于100，數(shù)字為

0

-

99例題一、數(shù)字三角形

738

8

1

0

2

7

4

4

4

5

2

6

5

在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經(jīng)過的數(shù)字之和最大。路徑上的每一步都只能往左下或右下走。只需要求出這個最大和即可，不必給出具體路徑。2021/5/92輸入格式：5//三角形行數(shù)。下面是三角形738810274445265要求輸出最大和

2021/5/93解題思路：

用二維數(shù)組存放數(shù)字三角形。

D(

r,

j)

:

第r行第

j

個數(shù)字(r,j從1開始算)

MaxSum(r,

j)

:

從D(r,j)到底邊的各條路徑中，

最佳路徑的數(shù)字之和。

問題：求

MaxSum(1,1)

典型的遞歸問題。

D(r,

j)出發(fā)，下一步只能走D(r+1,j)或者D(r+1,

j+1)。故對于N行的三角形：

if

(

r

==

N)

MaxSum(r,j)

=

D(r,j)

else

MaxSum(

r,

j)

=

Max{

MaxSum(r＋1,j),

MaxSum(r+1,j+1)

}+

D(r,j)2021/5/94int

D[MAX][MAX];int

n;int

MaxSum(int

i,

int

j){

if(i==n)

return

D[i][j];int

x

=

MaxSum(i+1,j);int

y

=

MaxSum(i+1,j+1);return

max(x,y)+D[i][j];}

數(shù)字三角形的遞歸程序:#include

<iostream>#include

<algorithm>#define

MAX

101using

namespace

std;int

main(){

int

i,j;

cin

>>

n;

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

cin

>>

D[i][j];cout

<<

MaxSum(1,1)

<<

endl;}2021/5/95

回答：重復(fù)計算為什么超時？

71

31

8101

8121

127343414154266451如果采用遞規(guī)的方法，深度遍歷每條路徑，存在大量重復(fù)計算。則時間復(fù)雜度為

2n,對于

n

=

100行，肯定超時。

2021/5/96如果每算出一個MaxSum(r,j)就保存起來，下次用到其值的時候直接取用，則可免去重復(fù)計算。那么可以用O(n2)時間完成計算。因為三角形的數(shù)字總數(shù)是

n(n+1)/2改進(jìn)2021/5/97數(shù)字三角形的記憶遞歸型動歸程序：#include

<iostream>#include

<algorithm>using

namespace

std;#define

MAX

101int

D[MAX][MAX];

int

n;int

maxSum[MAX][MAX];int

MaxSum(int

i,

int

j){

if(

maxSum[i][j]

!=

-1

)

return

maxSum[i][j];

if(i==n)

maxSum[i][j]

=

D[i][j];

else

{

int

x

=

MaxSum(i+1,j);

int

y

=

MaxSum(i+1,j+1);

maxSum[i][j]

=

max(x,y)+

D[i][j];}return

maxSum[i][j];}int

main(){

int

i,j;

cin

>>

n;

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

{

cin

>>

D[i][j];

maxSum[i][j]

=

-1;

}cout

<<

MaxSum(1,1)

<<

endl;

}2021/5/9845265738810274445265遞歸轉(zhuǎn)成遞推2021/5/99745265738810274445265遞歸轉(zhuǎn)成遞推2021/5/91071245265738810274445265遞歸轉(zhuǎn)成遞推2021/5/9117121045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/912712101045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/91320712101045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/9142013712101045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/915201310712101045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/916302321201310712101045265738810274445265遞歸轉(zhuǎn)成遞推2021/5/917#include

<iostream>#include

<algorithm>using

namespace

std;#define

MAX

101int

D[MAX][MAX];

int

n;int

maxSum[MAX][MAX];int

main()

{

int

i,j;

cin

>>

n;

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

cin

>>

D[i][j];

for(

int

i

=

1;i

<=

n;

++

i

)

maxSum[n][i]

=

D[n][i];for(

int

i

=

n-1;

i>=

1;--i

)

for(

int

j

=

1;

j

<=

i;

++j

)

maxSum[i][j]

=

max(maxSum[i+1][j],maxSum[i+1][j+1])

+

D[i][j]cout

<<

maxSum[1][1]

<<

endl;}2021/5/9184空間優(yōu)化

7

38

810

2744452655265

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/9197空間優(yōu)化

7

38

810

2744452655265

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/9207空間優(yōu)化

7

38

810

27444526512265

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/9217空間優(yōu)化

7

38

810

274445265121065

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/9227空間優(yōu)化

7

38

810

2744452651210105

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/92320空間優(yōu)化

7

38

810

2744452651210105

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/92420空間優(yōu)化

7

38

810

2744452651310105

沒必要用二維maxSum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組maxSum[100]即可,即只要存儲一行的MaxSum值就可以。

2021/5/925遞歸到動規(guī)的一般轉(zhuǎn)化方法

遞歸函數(shù)有n個參數(shù)，就定義一個n維的數(shù)組，數(shù)組的下標(biāo)是遞歸函數(shù)參數(shù)的取值范圍，數(shù)組元素的值是遞歸函數(shù)的返回值，這樣就可以從邊界值開始，逐步填充數(shù)組，相當(dāng)于計算遞歸函數(shù)值的逆過程。

2021/5/926動規(guī)解題的一般思路1.

將原問題分解為子問題

把原問題分解為若干個子問題，子問題和原問題形式相同或類似，只不過規(guī)模變小了。子問題都解決，原問題即解決(數(shù)字三角形例）。子問題的解一旦求出就會被保存，所以每個子問題只需求解一次。

2021/5/927動規(guī)解題的一般思路2.

確定狀態(tài)

在用動態(tài)規(guī)劃解題時，我們往往將和子問題相關(guān)的各個變量的一組取值，稱之為一個“狀態(tài)”。一個“狀態(tài)”對應(yīng)于一個或多個子問題，所謂某個“狀態(tài)”下的“值”，就是這個“狀態(tài)”所對應(yīng)的子問題的解。

2021/5/928動規(guī)解題的一般思路2.

確定狀態(tài)所有“狀態(tài)”的集合，構(gòu)成問題的“狀態(tài)空間”?！盃顟B(tài)空間”的大小，與用動態(tài)規(guī)劃解決問題的時間復(fù)雜度直接相關(guān)。在數(shù)字三角形的例子里，一共有N×(N+1)/2個數(shù)字，所以這個問題的狀態(tài)空間里一共就有N×(N+1)/2個狀態(tài)。整個問題的時間復(fù)雜度是狀態(tài)數(shù)目乘以計算每個狀態(tài)所需時間。在數(shù)字三角形里每個“狀態(tài)”只需要經(jīng)過一次，且在每個狀態(tài)上作計算所花的時間都是和N無關(guān)的常數(shù)。2021/5/929動規(guī)解題的一般思路2.

確定狀態(tài)

用動態(tài)規(guī)劃解題，經(jīng)常碰到的情況是，K個整型變量能構(gòu)成一個狀態(tài)（如數(shù)字三角形中的行號和列號這兩個變量構(gòu)成“狀態(tài)”）。如果這K個整型變量的取值范圍分別是N1,

N2,

……Nk，那么，我們就可以用一個K維的數(shù)組array[N1]

[N2]……[Nk]來存儲各個狀態(tài)的“值”。這個“值”未必就是一個整數(shù)或浮點(diǎn)數(shù)，可能是需要一個結(jié)構(gòu)才能表示的，那么array就可以是一個結(jié)構(gòu)數(shù)組。一個“狀態(tài)”下的“值”通常會是一個或多個子問題的解。2021/5/930動規(guī)解題的一般思路3.

確定一些初始狀態(tài)（邊界狀態(tài)）的值以“數(shù)字三角形”為例，初始狀態(tài)就是底邊數(shù)字，值就是底邊數(shù)字值。2021/5/931動規(guī)解題的一般思路4.

確定狀態(tài)轉(zhuǎn)移方程定義出什么是“狀態(tài)”，以及在該

“狀態(tài)”下的“值”后，就要找出不同的狀態(tài)之間如何遷移――即如何從一個或多個“值”已知的“狀態(tài)”，求出另一個“狀態(tài)”的“值”(“人人為我”遞推型)。狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉(zhuǎn)移方程”。數(shù)字三角形的狀態(tài)轉(zhuǎn)移方程:2021/5/932能用動規(guī)解決的問題的特點(diǎn)1)2)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。無后效性。當(dāng)前的若干個狀態(tài)值一旦確定，則此后過程的演變就只和這若干個狀態(tài)的值有關(guān)，和之前是采取哪種手段或經(jīng)過哪條路徑演變到當(dāng)前的這若干個狀態(tài)，沒有關(guān)系。2021/5/933例題二：最長上升子序列問題描述

一個數(shù)的序列ai，當(dāng)a1

<

a2

<

...

<

aS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1,

a2,

...,

aN)，我們可以得到一些上升的子序列(ai1,

ai2,

...,

aiK)，這里1

<=

i1

<i2

<

...

<

iK

<=

N。比如，對于序列(1,

7,

3,

5,

9,

4,

8)，有它的一些上升子序列，如(1,

7),

(3,

4,

8)等等。這些子序列中最長的長度是4，比如子序列(1,

3,

5,

8).你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。2021/5/934輸入數(shù)據(jù)輸入的第一行是序列的長度N

(1

<=

N

<=

1000)。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000。輸出要求最長上升子序列的長度。輸入樣例71

7

3

5

9

4

8輸出樣例42021/5/935解題思路1.找子問題

“求序列的前n個元素的最長上升子序列的長度”是個子問題，但這樣分解子問題，不具有“無后效性”

假設(shè)F(n)

=

x,但可能有多個序列滿足F(n)

=

x。有的序列的最后一個元素比

an+1小，則加上an+1就能形成更長上升子序列；有的序列最后一個元素不比an+1小……以后的事情受如何達(dá)到狀態(tài)n的影響，不符合“無后效性”2021/5/936解題思路1.找子問題“求以ak（k=1,

2,

3…N）為終點(diǎn)的最長上升子序列的長度”一個上升子序列中最右邊的那個數(shù)，稱為該子序列的“終點(diǎn)”。雖然這個子問題和原問題形式上并不完全一樣，但是只要這N個子問題都解決了，那么這N個子問題的解中，最大的那個就是整個問題的解。2021/5/9372.

確定狀態(tài)：子問題只和一個變量--

數(shù)字的位置相關(guān)。因此序列中數(shù)的位置k

就是“狀態(tài)”，而狀態(tài)

k

對應(yīng)的“值”，就是以ak做為“終點(diǎn)”的最長上升子序列的長度。狀態(tài)一共有N個。2021/5/9383.

找出狀態(tài)轉(zhuǎn)移方程：maxLen

(k)表示以ak做為“終點(diǎn)”的最長上升子序列的長度那么：初始狀態(tài)：maxLen

(1)

=

1maxLen

(k)

=

max

{

maxLen

(i)：1<=i

<

k

且

ai

<

ak且

k≠1

}

+

1若找不到這樣的i,則maxLen(k)

=

1

maxLen(k)的值，就是在ak左邊，“終點(diǎn)”數(shù)值小于ak

，且長度最大的那個上升子序列的長度再加1。因為ak左邊任何“終點(diǎn)”小于ak的子序列，加上ak后就能形成一個更長的上升子序列。2021/5/939#include

<iostream>#include

<cstring>#include

<algorithm>using

namespace

std;const

intint

a[MAXN];int

main()

{

int

N;int

maxLen[MAXN];

cin

>>

N;for(

int

i

=

1;i

<=

N;++i)

{cin

>>

a[i];maxLen[i]

=

1;}for(

int

i

=

2;

i

<=

N;

++i)

{//每次求以第i個數(shù)為終點(diǎn)的最長上升子序列的長度

for(

int

j

=

1;

j

<

i;

++j)

//察看以第j個數(shù)為終點(diǎn)的最長上升子序列

if(

a[i]

>

a[j]

)

maxLen[i]

=

max(maxLen[i],maxLen[j]+1);}cout

<<

*

max_element(maxLen+1,maxLen

+

N

+

1

);return

0;}

//時間復(fù)雜度O(N2)

“人人為我”遞推型動歸程序MAXN

=1010;2021/5/940動歸的常用兩種形式1）遞歸型優(yōu)點(diǎn)：直觀，容易編寫

缺點(diǎn)：可能會因遞歸層數(shù)太深導(dǎo)致爆棧，函數(shù)調(diào)用帶來額外時間開銷。無法使用滾動數(shù)組節(jié)省空間?？傮w來說，比遞推型慢。1）遞推型效率高，有可能使用滾動數(shù)組節(jié)省空間2021/5/941例三、最長公共子序列給出兩個字符串，求出這樣的一個最長的公共子序列的長度：子序列中的每個字符都能在兩個原串中找到，而且每個字符的先后順序和原串中的先后順序一致。2021/5/942最長公共子序列Sample

Inputabcfbc

abfcabprogramming

contestabcd

mnpSample

Output4202021/5/943

字符形成的子串的最長公共子序列的長度(i,j從0

開始算）

MaxLen(i,j)

就是本題的“狀態(tài)”假定

len1

=

strlen(s1),len2

=

strlen(s2）那么題目就是要求

MaxLen(len1,len2)最長

輸入兩個串s1,s2,公

設(shè)MaxLen(i,j)表示:共

s1的左邊i個字符形成的子串，與s2左邊的j個子序列2021/5/944顯然：MaxLen(n,0)

=

0

(

n=

0…len1）MaxLen(0,n)

=

0

(

n=0…len2）遞推公式：if

(

s1[i-1]

==

s2[j-1]

)

//s1的最左邊字符是s1[0]

MaxLen(i,j)

=

MaxLen(i-1,j-1)

+

1;else

MaxLen(i,j)

=

Max(MaxLen(i,j-1),MaxLen(i-1,j)

);時間復(fù)雜度O(mn)

m,n是兩個字串長度

最長公共子序列2021/5/945#include

<iostream>#include

<cstring>using

namespace

std;char

sz1[1000];char

sz2[1000];int

maxLen[1000][1000];int

main()

{while(

cin

>>

sz1

>>

sz2

)

{

int

length1

=

strlen(

sz1);

int

length2

=

strlen(

sz2);

int

nTmp;

int

i,j;for(

i

=

0;i

<=

length1;

i

++

)maxLen[i][0]

=

0;for(

j

=

0;j

<=

length2;

j

++

)maxLen[0][j]

=

0;2021/5/946

for(

i

=

1;i

<=

length1;i

++

)

{

for(

j

=

1;

j

<=

length2;

j

++

)

{

if(

sz1[i-1]

==

sz2[j-1]

)

maxLen[i][j]

=

maxLen[i-1][j-1]

+

1;

else

maxLen[i][j]

=

max(maxLen[i][j-1],

maxLen[i-1][j]);

}

}

cout

<<

maxLen[length1][length2]

<<

endl;}return

0;}2021/5/947怎么輸出這個最長公共子序列？回溯輸出2021/5/948voidLCS_LENGTH(charx[],chary[]){ inti,j,m=strlen(x),n=strlen(y); for(i=1;i<=m;i++)c[i][0]=0; for(j=1;j<=n;j++)c[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]='\\'; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]='^'; } else { c[i][j]=c[i][j-1]; b[i][j]='<'; }}voidLCS(charx[],inti,intj){ if(i&&j) { if(b[i][j]=='\\') { LCS(x,i-1,j-1); printf("%c",x[i-1]); } else if(b[i][j]=='^') LCS(x,i-1,j); else LCS(x,i,j-1); }}2021/5/949有一個由1..9組成的數(shù)字串.問如果將m個加號插入到這個數(shù)字串中,在各種可能形成的表達(dá)式中，值最小的那個表達(dá)式的值是多少例四、最佳加法表達(dá)式2021/5/950

假定數(shù)字串長度是n，添完加號后,表達(dá)式的最后一個加號添加在第

i

個數(shù)字后面，那么整個表達(dá)式的最小值，就等于在前

i

個數(shù)字中插入

m

–

1個加號所能形成的最小值，加上第

i

+

1到第

n個數(shù)字所組成的數(shù)的值（i從1開始算）。解題思路2021/5/951總時間復(fù)雜度：O(mn2)

.解題思路

設(shè)V(m,n)表示在n個數(shù)字中插入m個加號所能形成

的表達(dá)式最小值，那么：

if

m

=

0

V(m,n)

=

n個數(shù)字構(gòu)成的整數(shù)

else

if

n

<

m

+

1

V(m,n)

=

∞

else

V(m,n)

=

Min{

V(m-1,i)

+

Num(i+1,n)

}

(

i

=

m

…

n-1)

Num(i,j)表示從第i個數(shù)字到第j個數(shù)字所組成的數(shù)。數(shù)字編號從1開始算。此操

作復(fù)雜度是O(j-i+1)，可以預(yù)處理后存起來。2021/5/952總時間復(fù)雜度：O(mn2)

.若

n

比較大，long

long

不夠存放運(yùn)算過程中的整數(shù)，則需要使用高精度計算（用數(shù)組存放大整數(shù)，模擬列豎式做加法），復(fù)雜度為O(mn3)解題思路2021/5/953例五、神奇的口袋

有一個神奇的口袋，總的容積是40，用這個口袋可以變出一些物品，這些物品的總體積必須是40。John現(xiàn)在有n（1≤n

≤

20）個想要得到的物品，每個物品的體積分別是a1，a2……an。John可以從這些物品中選擇一些，如果選出的物體的總體積是40，那么利用這個神奇的口袋，John就可以得到這些物品?，F(xiàn)在的問題是，John有多少種不同的選擇物品的方式。

2021/5/954

3202020輸入輸入的第一行是正整數(shù)n

(1

<=

n

<=

20)，表示不同的物品的數(shù)目。接下來的n行，每行有一個1到40之間的正整數(shù)，分別給出a1，a2……an的值。輸出輸出不同的選擇物品的方式的數(shù)目。

輸入樣例

輸出樣例32021/5/955枚舉每個物品是選還是不選，共220種情況枚舉的解法：2021/5/956int

a[30];int

N;int

Ways(int

w

,int

k

)

{

//

從前k種物品中選擇一些，湊成體積w的做法數(shù)目

if(

w

==

0

)

return

1;

if(

k

<=

0

)

return

0;

return

Ways(w,

k

-1

)

+

Ways(w

-

a[k],

k

-1

);}int

main()

{

cin

>>

N;

for(

int

i

=

1;i

<=

N;

++

i

)

cin

>>

a[i];

cout

<<

Ways(40,N);

return

0;}遞歸解法

#include

<iostream>

using

namespace

std;2021/5/957#include

<iostream>using

namespace

std;int

a[30];

int

N;int

Ways[50][40];//Ways[i][j]表示從前j種物品里湊出體積i的方法數(shù)int

main()

{

cin

>>

N;

memset(Ways,0,sizeof(Ways));

for(

int

i

=

1;i

<=

N;

++

i

)

{

cin

>>

a[i];

Ways[0][i]

=

1;

}

Ways[0][0]

=

1;

for(

int

w

=

1

;

w

<=

40;

++

w

)

{

for(

int

k

=

1;

k

<=

N;

++

k

)

{

Ways[w][k]

=

Ways[w][k-1];

if(

w-a[k]

>=

0)

Ways[w][k]

+=

Ways[w-a[k]][k-1];

}

}

cout

<<

Ways[40][N];

return

0;}動規(guī)解法2021/5/958例六、0-1背包問題有N件物品和一個容積為M的背包。第i件物品的體積w[i]，價值是d[i]。求解將哪些物品裝入背包可使價值總和最大。每種物品只有一件，可以選擇放或者不放(N<=3500,M

<=

13000)。2021/5/9590-1背包問題用

F[i][j]

表示取前i種物品，使它們總體積不超過j的最優(yōu)取法取得的價值總和。要求F[N][M]邊界：if

(w[1]

<=

j)F[1][j]

=

d[1];elseF[1][j]

=

0;2021/5/9600-1背包問題用

F[i][j]

表示取前i種物品，使它們總體積不超過j的最優(yōu)取法取得的價值總和遞推：

F[i][j]

=

max(F[i-1][j],F[i-1][j-w[i]]+d[i])取或不取第

i種物品，兩者選優(yōu)(j-w[i]

>=

0才有第二項)2021/5/9610-1背包問題F[i][j]

=

max(F[i-1][j],F[i-1][j-w[i]]+d[i])

本題如用記憶型遞歸，需要一個很大的二維數(shù)組，會超內(nèi)存。注意到這個二維數(shù)組的下一行的值，只用到了上一行的正上方及左邊的值，因此可用滾動數(shù)組的思想，只要一行即可。即可以用一維數(shù)