動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法第1頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月前言：各類信息學(xué)競(jìng)賽的重要考察內(nèi)容。不同于其他算法和數(shù)據(jù)結(jié)構(gòu)，沒(méi)有固定的結(jié)構(gòu)框架。對(duì)選手能力有較高要求（函數(shù)思想）。初學(xué)者不易掌握其思想，需要做大量的題。典型的問(wèn)題。會(huì)做不代表真正掌握。主要是分析問(wèn)題的方法和思路；其次是代碼。2第2頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月在三個(gè)競(jìng)賽中的首次出現(xiàn)：數(shù)字三角形 【IOI1994】石子合并 【NOI1995】導(dǎo)彈攔截 【NOIP1999】3第3頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月目錄：兩個(gè)引例動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的常見模型及例題4第4頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月引例1：數(shù)字三角形【IOI1994】有一個(gè)數(shù)字三角形，從最頂層出發(fā)，每一步只能向左下或右下方向走。編程求從最頂層到最底層的一條路所經(jīng)過(guò)位置上的數(shù)字之和的最大值。下圖數(shù)據(jù)的路應(yīng)為: 7->3->8->7->5，和為30。輸入：第一行：n(1<=n<=100),數(shù)字三角形共有n行；以下R行：依次表示數(shù)字三角形中每行中的數(shù)字。每個(gè)數(shù)都是非負(fù)的，且<=100.輸出：一個(gè)正整數(shù)，路徑上數(shù)字之和的最大值。7388102744452655第5頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月6輸入樣例：5738810274445265輸出樣例：30第6頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月樣例：i,ji+1,ji+1,j+17第7頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月8第8頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月路徑數(shù)字最大和：7+3+8+7+5=309第9頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月深度優(yōu)先搜索算法：Proceduredfs(i,j,sum)//從(1,1)走到（i，j）位置所求和sumBeginifi=nthen//走到最后一行ans=max(ans,sum);exit;dfs(向左下方走)；dfs(向右下方走)；End;10第10頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月代碼實(shí)現(xiàn)：//二維數(shù)組a[i,j]存儲(chǔ)數(shù)字三角形。proceduredfs(i,j,sum:integer);beginifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;初始：dfs(1,1,a[1,1]);結(jié)果：ansi,ji+1,ji+1,j+111i,ji+1,ji+1,j+1第11頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月n<=100超時(shí)！12第12頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月N=109263531825146385932588470293882535020119968561497607471333951962796078786124494136303223163231325676748313第13頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月每個(gè)位置被計(jì)算過(guò)的次數(shù)：1111211331146411510105116152015611721353521711828567056288119368412612684369114第14頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月代碼實(shí)現(xiàn)：//二維數(shù)組a[i,j]存儲(chǔ)數(shù)字三角形。proceduredfs(i,j,sum:integer);begin

inc(count[i,j]);//全局計(jì)數(shù)器ifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;i,ji+1,ji+1,j+115第15頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月搜索速度慢的原因是做了很多重復(fù)的計(jì)算實(shí)際上：從（i,j）走到最后一行；路線上和的最大值不變。92635318251463859325884702938825

35020119968561497607471333951962796078786124494136303223163231325676748316第16頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月所以：第一次求完(i,j)到達(dá)最后一行的最大值后，用f[i,j]記錄下來(lái)。以后再遇到時(shí)不需要再搜索求解，可以直接使用f[i,j]，從而大大的節(jié)省時(shí)間。記憶化搜索17第17頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月記憶化搜索算法：//a[i,j]記錄數(shù)字三角形//f[i,j]:從(i,j)走到最后一行的和的最大值；初始-1Proceduredfs(i,j:integer);//求(i,j)到最后一行的最大和

beginifi=nthenbeginf[i,j]:=a[i,j];exit; end;

iff[i,j]>=0thenexit;//已經(jīng)求過(guò)了，無(wú)需再求dfs(i+1,j);dfs(i+1,j+1);f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];end;dfs(1,1);ans=f[1,1];18i,ji+1,ji+1,j+1第18頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月每個(gè)點(diǎn)的計(jì)算次數(shù)：n=101111111111111111111111111111111111111111111110000000000N<=100;問(wèn)題解決了19第19頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月思考記憶化搜索的求解過(guò)程：i,ji+1,ji+1,j+1……20f[i,j]:

(i,j)到最后一行的和的最大值；Ans=f[1,1]第20頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月?lián)Q一種方法實(shí)現(xiàn)：//f[i,j]

：從(i,j)走到最后一行的和的最大值；fori:=1tondof[n,i]:=a[n,i]; //最后一行fori:=n-1downto1do //從第n-1行向上求forj:=1toidof[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];writeln(f[1,1]);遞推法：倒推21第21頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月i,ji-1,j-1i,j順推：22f[i,j]

：從(1,1)走到(i,j)的和的最大值；Ans=max{f[n,i]}i:1..n第22頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月順推：//f[i,j]

：從(1,1)走到(i,j)的和的最大值；f[1,1]:=a[1,1];fori:=2tondoforj:=1toidof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];ans:=f[n,1]; //找最大的f[n,i]fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);23邊界情況?第23頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月24邊界問(wèn)題的解決：方法一：varf:array[0..100,0..100]oflongint;把第0行及第0列元素初始化為0。方法二：把f[i,1]和f[i,i]作為特殊情況單獨(dú)處理，即：fori:=2tondobeginf[i,1]=f[i-1,1]+a[i,1];f[i,i]=f[i-1,i-1]+a[i,i];forj:=2toi-1dof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];end;第24頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月回顧本題：重復(fù)的子問(wèn)題。用表記錄子問(wèn)題的解，以后可以直接使用。有明顯的階段性。求解方法：記憶化搜索；遞推。25第25頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月引例2：公共汽車【問(wèn)題描述】

一個(gè)城市的道路，南北向的路有n條，并由西向東從1標(biāo)記到n,東西向的路有m條，并從南向北從1標(biāo)記到m,每一個(gè)交叉點(diǎn)代表一個(gè)路口，有的路口有正在等車的乘客。一輛公共汽車將從(1,1)點(diǎn)駛到（n,m）點(diǎn)，車只能向東或者向北開.問(wèn)：司機(jī)怎么走能接到最多的乘客。nm(n,m)26北南西東第26頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月【輸入】第一行是n,m和k,其中k是有乘客的路口的個(gè)數(shù)。以下k行是有乘客的路口的坐標(biāo)和乘客的數(shù)量。已知每個(gè)路口的乘客數(shù)量不超過(guò)1000000。n,m<=1000.【輸出】接到的最多的乘客數(shù)。bus.inbus.out87114346242325612521552113117717428621127第27頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月a[i,j]:(i,j)位置的人數(shù);f[i,j]:從(1,1)走到(i,j)能接的最多人數(shù)。f[i,j]:=max{f[i-1,j],f[i,j-1]}+a[i,j]28第28頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月遞推實(shí)現(xiàn)：varf[0..1000,0..1000]oflongint;fillchar(f,sizeof(f),0);fori:=1tondo //按列forj:=1tomdo //按行f[i,j]:=max(f[i-1,j],f[i,j-1])+a[i,j];writeln(f[n,m]);29第29頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月二、動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃（DynamicProgramming簡(jiǎn)稱DP）。解決“多階段決策問(wèn)題”的一種高效算法。通過(guò)合理組合子問(wèn)題的解從而解決整個(gè)問(wèn)題解的一種算法。其中的子問(wèn)題并不是獨(dú)立的，這些子問(wèn)題又包含有公共的子子問(wèn)題?！瓌?dòng)態(tài)規(guī)劃算法就是對(duì)每個(gè)子問(wèn)題只求一次，并將其結(jié)果保存在一張表中(數(shù)組)，以后再用到時(shí)直接從表中拿過(guò)來(lái)使用，避免重復(fù)計(jì)算相同的子問(wèn)題?！安蛔鰺o(wú)用功”的求解模式，大大提高了程序的效率。動(dòng)態(tài)規(guī)劃算法常用于解決統(tǒng)計(jì)類問(wèn)題（統(tǒng)計(jì)方案總數(shù)）和最優(yōu)值問(wèn)題（最大值或最小值），尤其普遍用于最優(yōu)化問(wèn)題。30第30頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月定義：f[i,j]

：從(i,j)走到最后一行的和的最大值；目標(biāo)：f[1,1]倒推求解過(guò)程f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];31第31頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月

1、階段：

把所給求解問(wèn)題的過(guò)程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于按一定的次序去求解，過(guò)程不同，階段數(shù)就可能不同．描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用k表示。階段的劃分一般根據(jù)時(shí)間和空間來(lái)劃分的。

2、狀態(tài)：

某一階段的出發(fā)位置成為狀態(tài)，通常一個(gè)階段有多個(gè)狀態(tài)。

狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來(lái)描述，稱為狀態(tài)變量。

3、決策：

一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動(dòng)）稱為決策。描述決策的變量稱決策變量

4、策略和最優(yōu)策略

所有階段的決策有序組合構(gòu)成一個(gè)策略。

最優(yōu)效果的策略叫最優(yōu)策略。32動(dòng)態(tài)規(guī)劃的術(shù)語(yǔ)：第32頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月33例：最短路徑問(wèn)題

現(xiàn)在，我們想從城市A到達(dá)城市E。

怎樣走才能使得路徑最短，最短路徑的長(zhǎng)度是多少？AB1B2C1C2C3C4D1D2D3E531638438556343第33頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月34階段1階段2階段3階段4階段5第1部分：A第2部分：B1，B2第3部分：C1，C2，C3，C4第4部分：D1，D2，D3第5部分：EAB1B2C1C2C3C4D1D2D3E531638438556343第34頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月35定義f(i)為i點(diǎn)到E的最短距離，d(i,j)為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。倒推的方法來(lái)求A到E的最短距離。第5階段:f(E)=0;第4階段:f(D1)=3;f(D2)=4;f(D3)=3第3階段:f(C1)=min{d(C1,D1)+f(D1),d(C1,D2)+f(D2)}=min{8,10}=8f(C2)=d(C2,D1)+f(D1)=8f(C3)=d(C3,D3)+f(D3)=11f(C4)=d(C4,D3)+f(D3)=6第2階段:f(B1)=min{d(B1,C1)+f(C1),d(B1,C2)+f(C2),d(B1,C3)+f(C3)}=min{1+8,6+8,3+11}=9f(B2)=min{d(B2,C2)+f(c2),d(B2,C4)+f(C4)}=min{8+8,4+6}=10第1階段:f(A)=min{d(A,B1)+f(B1),d(A,B2)+f(B2)}=min{5+9,3+10}=13最短路徑：A->B2->C4->D3->E最短距離：13第35頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月36fk[x]=min{fk+1[yi]+d

[x,yi]}狀態(tài)轉(zhuǎn)移方程：由已求得的狀態(tài)來(lái)求未知狀態(tài)的遞推關(guān)系式稱為狀態(tài)轉(zhuǎn)移方程。Xy1y2yiEF[x]:x到終點(diǎn)的最短距離。目標(biāo)是f1[A]倒推：第36頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月37fk[x]=min{fk-1[yi]+d

[yi,x]}F[x]:起點(diǎn)到x最短距離。目標(biāo)是f5[E]順推：Xy1y2yiA第37頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月38一般形式：

U：狀態(tài)；

X：策略順推：f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}

L[Uk-1,Xk-1]：狀態(tài)Uk-1通過(guò)策略Xk-1到達(dá)狀態(tài)Uk

的費(fèi)用初始f[U1]；結(jié)果：f(Un)第38頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月39一般形式：

U：狀態(tài)；

X：策略倒推：

f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}

L[Uk,Xk]：狀態(tài)Uk通過(guò)策略Xk到達(dá)狀態(tài)Uk+1

的費(fèi)用初始f[Un]；結(jié)果：f(U1)第39頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月40動(dòng)態(tài)規(guī)劃問(wèn)題的特征:1、最優(yōu)子結(jié)構(gòu)

如果問(wèn)題的一個(gè)最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，則該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。也稱最優(yōu)化原理。最優(yōu)子結(jié)構(gòu)也可以理解為“整體最優(yōu)則局部最優(yōu)”。反之不一定成立。

2、重疊子問(wèn)題

在解決整個(gè)問(wèn)題時(shí)，要先解決其子問(wèn)題，要解決這些子問(wèn)題，又要先解決他們的子子問(wèn)題……。而這些子子問(wèn)題又不是相互獨(dú)立的，有很多是重復(fù)的，這些重復(fù)的子子問(wèn)題稱為重疊子問(wèn)題。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表中，以后再遇到這些相同問(wèn)題時(shí)直接查表就可以，而不需要再重復(fù)計(jì)算，每次查表的時(shí)間為常數(shù)。第40頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月3、無(wú)后效性原則41已經(jīng)求得的狀態(tài)，不受未求狀態(tài)的影響。第41頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月42最優(yōu)子結(jié)構(gòu)、重疊子問(wèn)題、無(wú)后效性階段1階段2階段3階段4階段5AB1B2C1C2C3C4D1D2D3E531638438556343第42頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月43第43頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月44拓?fù)鋱D（有向無(wú)環(huán)圖）無(wú)后效性第44頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月45非拓?fù)鋱D（可能有環(huán)）有后效性abc？bca？

abc51111第45頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月46動(dòng)態(tài)規(guī)劃的條件：

無(wú)后效性、最優(yōu)子問(wèn)題無(wú)后效性、最優(yōu)子問(wèn)題是否能滿足與狀態(tài)的表示、階段的劃分、狀態(tài)的轉(zhuǎn)移有關(guān)第46頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月47

1、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；

2、遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）；

3、以自底向上的方式計(jì)算出最優(yōu)值；

記憶化搜索（樹型）、遞推

4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。

設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟：第47頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月48狀態(tài)轉(zhuǎn)移方程的構(gòu)造是動(dòng)態(tài)規(guī)劃過(guò)程中最重要的一步,也是最難的一步.對(duì)于大多數(shù)的動(dòng)態(tài)規(guī)劃,尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道,就是尋找變化中的不變量（已經(jīng)求得的值）.定量處理的過(guò)程也就是決策實(shí)施的過(guò)程.動(dòng)態(tài)規(guī)劃的關(guān)鍵：第48頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月49f[Un]=初始值；fork←n-1downto1do//枚舉階段

forU取遍所有狀態(tài)do//枚舉狀態(tài)forX取遍所有決策do//枚舉決策f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}；

L[Uk,Xk]：狀態(tài)Uk通過(guò)策略Xk到達(dá)狀態(tài)Uk+1的費(fèi)用輸出：f[U1]:目標(biāo)動(dòng)態(tài)規(guī)劃的一般倒推格式為：第49頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月50//f[i,j]

：從(i,j)走到最后一行的和的最大值；fori:=1tondof[n,i]:=a[n,i]; //初始fori:=n-1downto1do //階段forj:=1toido //狀態(tài)f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]; //決策writeln(f[1,1]);第50頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月51f[U1]=初始值；fork←2tondo //枚舉每一個(gè)階段

forU取遍所有狀態(tài)doforX取遍所有決策dof[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}；

L[Uk-1,Xk-1]：狀態(tài)Uk-1通過(guò)策略Xk-1到達(dá)狀態(tài)Uk

的費(fèi)用輸出：f[Un]:目標(biāo)動(dòng)態(tài)規(guī)劃的一般順推格式為：第51頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月順推：//f[i,j]

：從(1,1)走到(i,j)的和的最大值；f[1,1]:=a[1,1]; //初始化fori:=2tondo //階段forj:=1toido //狀態(tài)f[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j]; //決策//找最大的f[n,i]ans:=f[n,1];fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);52第52頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月53貪心算法：采用“自頂向下”的方式使用最優(yōu)子結(jié)構(gòu)：先做決策，選在當(dāng)時(shí)看起來(lái)是最優(yōu)的選擇（只顧眼前利益），然后再求解決策后的那個(gè)子問(wèn)題。“先決策，再求解子問(wèn)題”DP:“先求得子問(wèn)題的解，然后決策”。73881027

4445265動(dòng)態(tài)規(guī)劃與貪心算法的不同：第53頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月通過(guò)做大量的題目，慢慢理解和體會(huì)DP其中的……54第54頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月三、DP常見模型55線性型坐標(biāo)型區(qū)間型背包型樹型動(dòng)態(tài)規(guī)劃有多種多樣的題目，通常按照狀態(tài)可分為以下幾類：第55頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月（一）、線性模型56線性動(dòng)態(tài)規(guī)劃狀態(tài)是一維的（f[i]）。正推：第i個(gè)元素的最優(yōu)值只與前i-1個(gè)元素的最優(yōu)值有關(guān)。倒推：第i個(gè)元素的最優(yōu)值只第i+1個(gè)元素之后的最優(yōu)值有關(guān)。經(jīng)典的線性DP題目有最長(zhǎng)上升子序列、最大連續(xù)子序列和、最長(zhǎng)公共子序列等。第56頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月1.最長(zhǎng)上升子序列模型57例1導(dǎo)彈攔截【NOIP1999】【問(wèn)題描述】某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，研發(fā)出一種導(dǎo)彈攔截系統(tǒng)，但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都要高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲，由于該系統(tǒng)還在試用階段，不能攔截所有的導(dǎo)彈，輸入敵國(guó)導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），請(qǐng)聰明的你幫忙計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。【輸入】第一行：n（<=1000），敵國(guó)導(dǎo)彈的數(shù)量。第二行：n個(gè)整數(shù)，用空格分隔，依次是敵國(guó)導(dǎo)彈的高度(<30000)?！据敵觥孔疃鄶r截?cái)硣?guó)導(dǎo)彈的數(shù)量?！緮?shù)據(jù)規(guī)?！繉?duì)于100%的數(shù)據(jù)：n<=1000。第57頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月58【樣例輸入輸出】bumb.inbumb.out8271910123

4

題意簡(jiǎn)述：

給定n個(gè)元素的數(shù)列，求最長(zhǎng)的上升子序列長(zhǎng)度。即：在原序列中，最多能選多少個(gè)數(shù)，在原有順序下遞增。第58頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月最長(zhǎng)上升子序列長(zhǎng)度（LIS）：59最長(zhǎng)上升子序列顯然是以某一個(gè)a[i]作為第一元素的一個(gè)最長(zhǎng)上升子序列。如果求出以原序列中每一個(gè)元素a[i]作為第一個(gè)元素開頭的最長(zhǎng)上升子序列長(zhǎng)度f(wàn)[i].那么:ans=max{f[i]}；i=1..n問(wèn)題是怎么求f[i]?8271910143第59頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月倒推法：60a[i]:數(shù)列中的第i個(gè)數(shù)。f[i]:以a[i]為開始(a[i]是被選中的第一個(gè)元素)的最長(zhǎng)遞增子序列的序列長(zhǎng)度。轉(zhuǎn)移方程：f[i]=max{f[j]}+1條件：i<j<=n并且a[i]<a[j]邊界：f[n]=1;目標(biāo)：max{f[i]};1<=i<=n8271910143第60頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月倒推參考程序：61f[n]:=1;fori:=n-1downto1dobeginforj:=i+1tondoif(a[j]>a[i])and(f[j]>f[i])thenf[i]:=f[j]; //找最大的f[j]inc(f[i]); //包含a[i]end;ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];writeln(ans);第61頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月順推：62a[i]:數(shù)列中的第i個(gè)數(shù)。f[i]:以a[i]為結(jié)尾(a[i]是被選中的最后一個(gè)元素)的最長(zhǎng)遞增子序列的序列長(zhǎng)度。f[i]=max{f[j]}+1

條件：1<=j<i并且a[j]<a[i]邊界：f[1]=1;目標(biāo)：max{f[i]};1<=i<=n8271910143第62頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月順推參考程序：63f[1]:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])and(f[j]>f[i])thenf[i]:=f[j]; //找最大的f[j]inc(f[i]); //包含a[i]end;ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];writeln(ans);第63頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月最長(zhǎng)上升子序列長(zhǎng)度（LIS）：64

倒推：f[i]:以a[i]為開始元素的最長(zhǎng)遞增子序列的序列長(zhǎng)度。轉(zhuǎn)移方程：f[i]=max{f[j]}+1條件：i<j<=n并且a[i]<a[j]邊界：f[n]=1;目標(biāo)：max{f[i]};1<=i<=n第64頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月順推：65f[i]:以a[i]為結(jié)尾的最長(zhǎng)遞增子序列的序列長(zhǎng)度。f[i]=max{f[j]}+1

條件：1<=j<i并且a[j]<a[i]邊界：f[1]=1;目標(biāo)：max{f[i]};1<=i<=n時(shí)間復(fù)雜度：O(n2)第65頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月知識(shí)擴(kuò)展：66最長(zhǎng)上升子序列長(zhǎng)度； <最長(zhǎng)不下降子序列長(zhǎng)度； <=最長(zhǎng)下降子序列長(zhǎng)度；

>最長(zhǎng)不上升子序列長(zhǎng)度。 >=第66頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例2：合唱隊(duì)形[NOIP2004]67【問(wèn)題描述】N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，……，K，他們的身高分別為T1,T2,……,Tk,則他們的身高滿足T1<T2<……Ti，Ti>Ti+1>……>Tk(1<=i<=K)。你的任務(wù)是：已知有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。第67頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月68【樣例輸入輸出】chorus.inchorus.out8186186150200160130197220

4【輸入】第一行是一個(gè)整數(shù)N(2<=N<=1000),表示同學(xué)的總數(shù)。第二行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高（厘米）?！据敵觥恳粋€(gè)整數(shù)，表示最少需要幾位同學(xué)出列?！緮?shù)據(jù)規(guī)?！繉?duì)與全部的數(shù)據(jù)，保證有n<=1000。第68頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月問(wèn)題分析:69計(jì)算最少需要幾位同學(xué)出列，可轉(zhuǎn)化為計(jì)算最多能留下多少同學(xué)。將所有合唱隊(duì)形同學(xué)排為一列，在二維坐標(biāo)系中根據(jù)身高描點(diǎn)連線，圖樣就像一座山峰。隊(duì)列左邊的身高依次上升，右邊依次下降，中間有一個(gè)最高點(diǎn)，而這個(gè)最高點(diǎn)的左側(cè)是上升子序列，右側(cè)是下降子序列。人數(shù)最多是最優(yōu)合唱隊(duì)形。第69頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月算法描述：70對(duì)整個(gè)身高序列a[i]做：一次最長(zhǎng)上升子序列(f[i])：正推求；一次最長(zhǎng)下降子序列(g[i])：倒推求；之后枚舉最高點(diǎn)a[i]:ans=max(f[i]+g[i]-1)是保留最大值。最少出隊(duì)列人數(shù):n-ans.第70頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月參考代碼：71a[i]:身高。f[i]:以a[i]為最后一個(gè)人最長(zhǎng)上升子序列長(zhǎng)度

f[1]:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])and(f[j]>f[i])thenf[i]:=f[j];inc(f[i]);end;第71頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月72//g[i]:以a[i]開頭的最長(zhǎng)下降子序列長(zhǎng)度g[n]:=1;fori:=n-1downto1dobeginforj:=i+1tondoif(a[j]<a[i])and(g[j]>g[i])theng[i]:=g[j];inc(g[i]);end;

第72頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月枚舉以第i位同學(xué)為最高的隊(duì)形：73ans:=0;//保留的最多人數(shù)。fori:=1tondoiff[i]+g[i]-1>ansthenans:=f[i]+g[i]-1;writeln(n-ans);//最少出隊(duì)人數(shù)第73頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例3：上帝選人74【問(wèn)題描述】

世界上的人都有智商IQ和情商EQ。我們用兩個(gè)數(shù)字來(lái)表示人的智商和情商，數(shù)字大就代表其相應(yīng)智商或情商高?，F(xiàn)在你面前有N個(gè)人，這N個(gè)人的智商和情商均已知，請(qǐng)你選擇出盡量多的人，要求選出的人中不存在任意兩人i和j，i的智商大于j的智商但i的情商小于j的情商?！据斎搿康谝恍幸粋€(gè)正整數(shù)N，表示人的數(shù)量。第二行至第N+1行，每行兩個(gè)正整數(shù)，分別表示每個(gè)人的智商和情商?！据敵觥?jī)H一行，為最多選出的人的個(gè)數(shù)。第74頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月75【數(shù)據(jù)規(guī)模和約定】N<=1000；【輸入輸出樣例】select.inselect.out310010012090110802第75頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月問(wèn)題分析：76原題中的要求“不存在任意兩人i和j，i的智商大于j的智商，但i的情商小于j的情商?！睂⑵滢D(zhuǎn)化成：就是要求不存在i,j滿足：

如果（iq[i]>iq[j]），但(eq[i]<eq[j])。即選出的人i和j要滿足：(IQ[i]>=IQ[j])and(EQ[i]>=EQ[j])或者(IQ[i]<=IQ[j])and(EQ[i]<=EQ[j])第76頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月再形象一點(diǎn)：7780901002507085100120第77頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月78對(duì)于所有選出的人：當(dāng)IQ有序時(shí)，EQ必定是有序的（連線不相交）。同序80901002507085100120第78頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月79IQEQ10269211219815IQEQ81592110261219第79頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月80IQEQ115106106105IQEQ105106106115第80頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月設(shè)計(jì)算法：811.將所有人IQ（或者EQ）從小到大排序。2.求EQ（或者IQ）的最長(zhǎng)非遞減子序列長(zhǎng)度.第81頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例4：遞增子序列最大和82【問(wèn)題描述】給定長(zhǎng)度為n的正整數(shù)序列a1,a2,…,an。求一個(gè)遞增的子序列，和最大?！据斎搿康谝恍?，n，表示給定序列的個(gè)數(shù)。第二行，n個(gè)用空格隔開的正整數(shù)。【輸出】遞增子序列的最大和?！緮?shù)據(jù)范圍限制】n<=1000,0<ai<=109。第82頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月83【輸入輸出樣例】Sum.inSum.out6241205626遞增的子序列最大和：2+4+20=26。不是最長(zhǎng)遞增子序列LIS而是簡(jiǎn)單變形！第83頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月算法描述：84定義f[i]表示以a[i]為最后一個(gè)數(shù)的遞增子序列的最大和。2412056f[i]:=max(f[j])+a[i]

（1<=j<i且a[j]<a[i]）Ans=max{f[i]}i=1..n時(shí)間：O(n*n)第84頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月參考代碼：85f[1]:=a[1];ans:=0;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])thenf[i]:=max(f[i],f[j]);f[i]:=f[i]+a[i];end;fori:=1tondoiff[i]>ansthenans:=f[i];writeln(ans);第85頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月2：最大連續(xù)子序列的和模型86求給定序列的最大連續(xù)子序列和。輸入：第一行：n（n<100000）第二行：n個(gè)整數(shù)[-3000，3000]。輸出：最大連續(xù)子序列的和。樣例：輸入：7-64-13

2-32輸出：8例5第86頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月87算法1：枚舉任意連續(xù)區(qū)間[i,j]求和找最大值ans:=-300000000;fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsum>ansthenans:=sum;end;writeln(ans);時(shí)間：O(n3)第87頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月88算法2：算法1的稍加改進(jìn)ans:=-300000000;fori:=1tondobeginsum:=0;forj:=itondobeginsum:=sum+a[j];ifsum>ansthenans:=sum;end;end;writeln(ans);時(shí)間：O(n2)第88頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月891、以a[i]為結(jié)束點(diǎn)和以a[i-1]為結(jié)束點(diǎn)的最大連續(xù)子序列和有沒(méi)有聯(lián)系？有什么樣的聯(lián)系？2、如果事先已經(jīng)求得了以a[i-1]為結(jié)束點(diǎn)的最大連續(xù)子序列和為x，那么怎樣求以a[i]為結(jié)束點(diǎn)的最大連續(xù)子序列？-64-132-32繼續(xù)分析：第89頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月90a[i]:序列；f[i]：以a[i]為終點(diǎn)（連續(xù)區(qū)間的右邊界）的子序列的最大和。時(shí)間：O(n)順推法：f[i]=max{f[i-1]+a[i],a[i]}=max{f[i-1],0}+a[i]初始：f[1]=a[1]目標(biāo)：max{f[i]}(1<=i<=n)第90頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月91f[1]:=a[1];fori:=2tondof[i]:=max(f[i-1]+a[i],a[i]);ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];

第91頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月92a[i]:序列；f[i]:從第i項(xiàng)開始(以第i項(xiàng)為第1項(xiàng))的最大連續(xù)子序列的和。f[i]=max{f[i+1]+a[i],a[i]}初始：f[n]=a[n]目標(biāo)：max{f[i]}1<=i<=n-64-132-32倒推法：第92頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月93f[n]:=a[n];fori:=n-1downto1dof[i]:=max(a[i]+f[i+1],a[i]);

ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];

第93頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月94ans:=0;s:=0;fori:=1tondobegins:=s+a[i];ifs<0thens:=0;ifs>ansthenans:=s;end;writeln(ans);進(jìn)一步分析上面的兩種求解方法，新序列要么是在現(xiàn)有某序列的一端添加一個(gè)元素，要么是只包含該元素。第94頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例6：勤工儉學(xué)（下午上機(jī)題目）95f[0]:=0;d[0]:=0;fori:=1tondobeginiff[i-1]>0thenbeginf[i]:=f[i-1]+a[i];

d[i]:=d[i-1]+1;endelsebeginf[i]:=a[i];d[i]:=1;end;end;第95頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月3.最長(zhǎng)公共子序列問(wèn)題LCS96最長(zhǎng)公共子序列也稱作最長(zhǎng)公共子串(不要求一定連續(xù))，英文縮寫為L(zhǎng)CS（LongestCommonSubsequence）。

其定義是，一個(gè)序列S，如果分別是兩個(gè)或多個(gè)已知序列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則S稱為已知序列的最長(zhǎng)公共子序列。第96頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月97給定兩個(gè)序列

X={x1,x2,...,xm}

Y={y1,y2,...,yn}

求X和Y的一個(gè)最長(zhǎng)公共子序列舉例

X={a,b,c,b,d,a,b}

Y={b,d,c,a,b,a}

最長(zhǎng)公共子序列為

LSC={b,c,b,a}

例7：第97頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月98要求：X和Y以字符串輸入，長(zhǎng)度<=1000.輸出：最長(zhǎng)公共子串的長(zhǎng)度如：輸入：abcbdab

bdcaba輸出4LCS=bcba

第98頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月分析：99X=‘a(chǎn)bcdefgh’Y=‘a(chǎn)cneh’X=‘a(chǎn)bcdefgh’Y=‘a(chǎn)cnehk’X=‘a(chǎn)bcdefgkh’Y=‘a(chǎn)cnehk’X=‘a(chǎn)bcdefgn’Y=‘a(chǎn)cnem’第99頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月分析：100X={x1,...,xi-1

，xi}

Y={y1,...,yj-1

，yj}f[i,j]:x的前i個(gè)和y的前j個(gè)字符的最大公共子序列長(zhǎng)度。xi=yj時(shí),f[i,j]=f[i-1,j-1]+1

xi<>yj時(shí),f[i,j]=max{f[i,j-1],f[i-1,j]}第100頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月參考代碼：101fori:=1tondo //X的長(zhǎng)度f(wàn)orj:=1tomdo //Y的長(zhǎng)度beginf[i,j]:=0;ifx[i]=y[j]thenf[i,j]:=f[i-1,j-1]+1elsef[i,j]:=max(f[i-1,j],f[i,j-1]);end;第101頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月（二）坐標(biāo)類模型102比較簡(jiǎn)單的一類動(dòng)態(tài)規(guī)劃問(wèn)題。常以二維空間坐標(biāo)系為模板展開，因此狀態(tài)轉(zhuǎn)移方程也在坐標(biāo)系中尋找，一般定義f[i,j]表示狀態(tài)，此狀態(tài)表示某個(gè)點(diǎn)的坐標(biāo)。有關(guān)系的狀態(tài)：f[i-1,j]，f[i,j-1]，f[i-1,j-1]按行或列的順序求解問(wèn)題。第102頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月引例1：數(shù)字三角形【IOI1994】有一個(gè)數(shù)字三角形，從最頂層出發(fā)，每一步只能向左下或右下方向走。編程求從最頂層到最底層的一條路所經(jīng)過(guò)位置上的數(shù)字之和的最大值。下圖數(shù)據(jù)的路應(yīng)為: 7->3->8->7->5，和為30。輸入：第一行：n(1<=n<=100),數(shù)字三角形共有n行；以下R行：依次表示數(shù)字三角形中每行中的數(shù)字。每個(gè)數(shù)都是非負(fù)的，且<=100.輸出：一個(gè)正整數(shù)，路徑上數(shù)字之和的最大值。738810274445265103第103頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月引例2：公共汽車【問(wèn)題描述】

一個(gè)城市的道路，南北向的路有n條，并由西向東從1標(biāo)記到n,東西向的路有m條，并從南向北從1標(biāo)記到m,每一個(gè)交叉點(diǎn)代表一個(gè)路口，有的路口有正在等車的乘客。一輛公共汽車將從(1,1)點(diǎn)駛到（n,m）點(diǎn)，車只能向東或者向北開.問(wèn)：司機(jī)怎么走能接到最多的乘客。nm(n,m)104北南西東第104頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例8：最大正方形面積105【題目描述】給定一個(gè)R行C列的01矩陣，求一個(gè)最大的正方形全1子矩陣，并輸出該最大正方形子矩陣的面積?！据斎搿康谝恍薪o出兩個(gè)正整數(shù)R,C，表示矩陣有R行C列；接下來(lái)R行C列給出這個(gè)01矩陣，行內(nèi)相鄰兩元素用一個(gè)空格隔開。R,C<=1000。第105頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月106樣例：matrix.inmatrix.out5800011101110111110111110110111110111011019

第106頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月f[i,j]定義為以(i,j)為右下角頂點(diǎn)的最大正方形邊長(zhǎng)。最大正方形邊長(zhǎng)：ans=max{f[i,j]}1<=i<=R，1<=j<=C。最大面積：ans*ans107第107頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月108Ifa[i,j]=0thenf[i,j]:=0;(i,j)(i-1,j-1)（i,j-1）(i-1,j)第108頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月1111情況1：？(i,j)(i-1,j)(i-1,j-1)(i,j-1)f[i,j]=f[i-1,j]+1109第109頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月1111？f[i,j]=f[i-1,j-1]+1情況2：110第110頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月1111圖3？f[i,j]=f[i,j-1]+1情況3：111第111頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月當(dāng)a[i,j]=1f[i,j]:=min{f[i,j-1],f[i-1,j],f[i-1,j-1]}+1;綜上三種情況：112第112頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月數(shù)字三角形2有一個(gè)數(shù)字三角形，從最頂層出發(fā)，每一步只能向左下或右下方向走。編程求從最頂層到最底層的一條路所經(jīng)過(guò)位置上的數(shù)字之和mod100的最大值。輸入：第一行：n(1<=n<=25),數(shù)字三角形共有n行；以下R行：依次表示數(shù)字三角形中每行中的數(shù)字。每個(gè)數(shù)都是非負(fù)的，且<=100.輸出：一個(gè)正整數(shù)，路徑上數(shù)字之和mod100的最大值。19998111113第113頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月114定義f[i,j]表示到達(dá)第i行第j列位置的最優(yōu)值，則：f[i,j]=Max{ (f[i-1,j-1]+a[i,j])mod100,(f[i-1,j]+a[i,j])mod100}初始值：f[1,1]=a[1,1].max{f[n,i]}即為所求。錯(cuò)誤作法！因?yàn)椴痪邆渥顑?yōu)子結(jié)構(gòu)。第114頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月115正確作法：定義f[i,j,k]表示到達(dá)第i行第j列位置能否得到k。(0<=k<=99).f[i,j,k]=f[i,j,k]or f[i-1,j-1,(k-a[i,j]+100)mod100]or f[i-1,j,(k-a[i,j]+100)mod100];初始值:f[1,1,a[1,1]]=true,其余均為false.第115頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月（三）背包類模型116背包問(wèn)題九講第116頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月有一個(gè)背包，最大載重量為m。有n種貨物：重量為W[i](<1000)；

價(jià)值為V[i](<1000).今從ｎ種物品中選取若干件放入背包，使其重量之和不超過(guò)m，而所選貨物的價(jià)值之和為最大。n<=100,m<1000.

求最大價(jià)值。例9：01背包基本模型117第117頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月118輸入樣例1：

410

4357

1572025

輸出樣例1：

35輸入樣例2：

420

291015

291016

輸出樣例2：

19價(jià)值大的？單位價(jià)值大的？第118頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月proceduredfs(i,left,value:longint);//在前i件物品中選了若干件放入到背包中，其價(jià)值為value，背包還能裝的重量為left。beginifi=nthenifvalue>ansthenans:=value;

ifi=nthenexit; //防止越界

dfs(i+1,left,value); //不裝i+1ifleft>=w[i+1]then //裝i+1

dfs(i+1,left-w[i+1],value+v[i+1]);end;深度優(yōu)先搜索算法:119第119頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月n<=100時(shí)間:O(2n)dfs(0,m,0);120第120頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0--10物品0--4編號(hào)1234容量4357價(jià)值15720254件物品背包容量：10算法2：設(shè)f[i,j]:從1到i件物品中選取若干件放到容量為j的背包中，獲得的最大價(jià)值。目標(biāo)是：f[n,m]121第121頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月用f[i,j]表示在第１到第i件物品中選擇若干件到載重量為j的背包中所能獲得的最大價(jià)值．f[i,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]:(j>=w[i])}(1<=i<=n,1<=j<=m)目標(biāo)：f[n,m];2)f[i-1,j-W[i]]+V[i]：

放第i件的價(jià)值。條件：j>=w[i]1)f[i-1,j]:不放第i件物品獲得的價(jià)值。122第122頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月主程序：fori:=1tondo

forj:=1tomdobeginf[i,j]:=f[i-1,j];

//不選擇第i件物品

if(j>=w[i])and(f[i,j]<f[i-1,j-w[i]]+v[i]) //選擇第i件物品

thenf[i,j]:=f[i-1,j-w[i]]+v[i];end;writeln(f[n,m]);end.123第123頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月對(duì)于從1到N（1<=N<=39）的連續(xù)整數(shù)集合，劃分成兩個(gè)子集合，使得每個(gè)集合的數(shù)字之和相等。舉個(gè)例子，如果N=3，對(duì)于{1，2，3}能劃分成兩個(gè)子集合，他們每個(gè)的所有數(shù)字和是相等的：{3}and{1,2}這是唯一的一種分法（交換集合位置被認(rèn)為是同一種劃分方案，因此不會(huì)增加劃分方案總數(shù)）。如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分法的子集合各數(shù)字和是相等的:{1,6,7}and{2,3,4,5};{2,5,7}and{1,3,4,6};{3,4,7}and{1,2,5,6};{1,2,4,7}and{3,5,6}集合劃分（subset）124第124頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月125分析：如果用搜索算法求解，但效率較低，剪枝優(yōu)化效果不夠理想。1+2+…+n=n*(n+1)div2考慮n*(n+1)mod4的取值：nmod4=1或2時(shí)，方案數(shù)為0;nmod4=0或3時(shí)：第125頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月令s=n*(n+1)div4問(wèn)題轉(zhuǎn)化為從1···n中取數(shù)，得到和為s的取數(shù)方法有多少種。為避免重復(fù)，不取數(shù)字1，f(i,j)表示從i···n中取數(shù)得到和為j的方案數(shù)，則：f(i,j)=f(i+1,j)+f(i+1,j-i)(2<=i<=n,0<=j<=s);f(n,0)=1;f(n,n)=1;其它值為0.f(2,s)即為題目的解。126第126頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月fillchar(f,sizeof(f),0);f[n,0]:=1;f[n,n]:=1;fori:=n-1downto2doforj:=0ton*(n+1)div4dobeginf[i,j]:=f[i+1,j];ifj-i>=0thenf[i,j]:=f[i,j]+f[i+1,j-i];end;writeln(f[2,n*(n+1)div4]);127第127頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月(四)區(qū)間型模型128區(qū)間型動(dòng)態(tài)規(guī)劃是線性動(dòng)態(tài)規(guī)劃的拓展，它將區(qū)間長(zhǎng)度作為階段，長(zhǎng)區(qū)間的答案與短區(qū)間有關(guān)。在求解長(zhǎng)區(qū)間答案前需先將短區(qū)間答案求出。區(qū)間型動(dòng)態(tài)規(guī)劃的典型應(yīng)用有石子合并、乘積最大等。第128頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例10：石子合并129有N堆石子(N≤100)排成一排?，F(xiàn)要將石子合并成一堆.規(guī)定每次只能選相鄰的兩堆合并成一堆新的石子,并將新的一堆的石子數(shù),記為該次合并的得分.

選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少。

輸入數(shù)據(jù):

第一行為石子堆數(shù)N;

第二行為每堆石子數(shù)。輸出數(shù)據(jù):

合并石子后得到的最小得分。第129頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月130如:41352最小得分：22貪心算法：

每次合并相鄰兩堆和最小的那兩堆。第130頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月反例：7447131貪心：8+15+22=45正確：11+11+22=44第131頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月應(yīng)該怎么合并呢？1323堆石子合并方案：11+（11+6）=289+（8+9）=26Ans=Min(28,26)=26836第132頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月133N=4時(shí)，4堆一共合并了幾次？最后一次合并成一堆前的那兩堆什么樣？8，18

或者13,13

或者18,8哪種情況是理想的情況：min（8+18,13+13,18+8）=26子問(wèn)題變成3堆和2堆的情況。8558第133頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月5堆石子：134(1,5)=min{(1,1)+(2,5);(1,2)+(3,5)；(1,3)+(4,5);(1,4)+(5,5)}+sum[1,5]第134頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月n堆石子：n-1次合并135a1,a2,a3,…,an-1,anmin{(1..k)+(k+1..n)}+sum[1,n]

枚舉：k=1..n-1重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)(1,n)=min{(1,1)+(2,n);(1,2)+(3,n)；…(1,n-1)+(n,n)}+sum[1,n]第135頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月動(dòng)態(tài)規(guī)劃算法：136定義f[i,j]表示從第i到第j堆間合并為一堆的最小代價(jià)。a[i],……,a[j]共有j-i+1堆石子sum[i,j]=a[i]+a[i+1]+…+a[j]狀態(tài)轉(zhuǎn)移方程：f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j]

枚舉位置k：i<=k<=j-1初始：f[i,i]=0;ans=f[1,n]第136頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月實(shí)現(xiàn)方法1：記憶化搜索137a[i]:記錄第i堆石子數(shù)量。s[i]=a[1]+a[2]+…+a[i]。//前綴和sum[i,j]=s[j]-s[i-1].readln(n);s[0]:=0;fori:=1tondobeginread(a[i]);s[i]:=s[i-1]+a[i];end;第137頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月搜索過(guò)程：138functiondfs(i,j:longint):longint; //合并i..jvark:longint;beginifi=jthenexit(0); //初始f[i,j]:=0;

iff[i,j]>0thenexit(f[i,j]); //已經(jīng)求過(guò)f[i,j]:=maxlongint;/ /為求最小值準(zhǔn)備fork:=itoj-1dof[i,j]:=min(f[i,j],

dfs(i,k)+dfs(k+1,j)+s[j]-s[i-1]);exit(f[i,j]); //dfs=f[i,j]返回函數(shù)值end;第138頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月139072036476101025344801120340717060346524123456123456f[i,j]:第i到第j堆間合并為一堆的最小代價(jià)。f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j]第139頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月140f[2,5]=min(f[2,2]+f[3,5];f[2,3]+f[4,5];f[2,4]+f[5,5])+sum[2,5]=min(20,10+7,25)+17=34第140頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月遞推法：合并第i堆到第j堆141fori:=1tondof[i,i]:=0;{初始化}forp:=1ton-1do//合并的堆數(shù)p:階段fori:=1ton-pdo//枚舉狀態(tài)：beginj:=i+p;f[i,j]:=maxlongint;fork:=itoj-1do{枚舉決策}

f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]);f[i,j]:=f[i,j]+s[j]-s[i-1];end;時(shí)間:O(n3)第141頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月總結(jié)本題：1421、前綴和的應(yīng)用。2、區(qū)間的dp的求解方法：

不能順推也不能倒推。是以區(qū)間長(zhǎng)度的大小劃分階段。按區(qū)間從小到大的順序劃分。第142頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月擴(kuò)展一下：NOI95143石子由一排改為圍成一個(gè)環(huán)的形狀？45944594459第143頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月14445944594459第144頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月環(huán)形石子合并算法：145環(huán)變成線性:長(zhǎng)度:2n-1a[1],a[2]......a[n],a[n+1].....a[2n-1];a[n+i]=a[i]f[i,j]:合并i到j(luò)堆的最小得分。f[i,j]=min{f[i,k]+f[k+1,j]}+s[j]-s[i-1].(i<=k<=j-1)目標(biāo)：ans=min{f[1,n],f[2,n+1],...,f[n,2n-1]}timeO(n^3)}第145頁(yè)，課件共169頁(yè)，創(chuàng)作于2023年2月例11：括號(hào)序列146

定義一個(gè)合法的括號(hào)序列：（1）空序列是合法的（2）假如S是一個(gè)合法的序列，則(S)和[S]都是合法的（3）假如A和B都是合法的，那么AB和BA也是合法的例如以下是合法的括號(hào)序列：(),[],(()),([]),()[],()[()]以下是不合法括號(hào)序列的：(,[,],)(,([),([()，([)]給定一些由‘(’,‘