2024-2025NOIP-算法(中國(guó)計(jì)算機(jī)學(xué)會(huì)編)

2024-2025NOIP好用算法

中國(guó)計(jì)算機(jī)學(xué)會(huì)2024

1.模擬方法.................................................................................3

a.用數(shù)學(xué)量和圖形描述問題...............................................................3

b.模擬計(jì)算過程.........................................................................3

C.模擬時(shí)的優(yōu)化.........................................................................3

d.高精度計(jì)算算法.......................................................................4

習(xí)題....................................................................................5

2.排序算法與算法時(shí)空困難度...............................6

a.簡(jiǎn)潔排序算法.........................................................................6

b.快速排序、堆排序.....................................................................6

c.算法時(shí)空困難度.....................................................................”.7

d.時(shí)空的簡(jiǎn)潔優(yōu)化方法...................................................................8

e.線性時(shí)間排序.........................................................................8

f.歸并排序..............................................................................9

g.合理選用排序算法.....................................................................9

習(xí)題.....................................................................................9

3.搜尋.....................................................................................10

a.困難的模擬問題與利用相像性...........................................................10

b.函數(shù)的遞歸調(diào)用......................................................................10

c.棧與深度優(yōu)先搜尋...................................................................“11

d.深度優(yōu)先搜尋的優(yōu)化...................................................................12

仁隊(duì)列與廣度優(yōu)先搜尋...................................................................12

f.廣度優(yōu)先搜尋的優(yōu)化.....................................12

習(xí)題....................................................................................13

4.貪心方法................................................................................14

a.工程支配模型.........................................................................14

b.部分背包與每步最優(yōu)...................................................................14

C.構(gòu)造貪心算法.........................................................................15

習(xí)題....................................................................................15

5.動(dòng)態(tài)規(guī)劃................................................................................16

a.另一種形式的工程支配.................................................................16

b.記憶化搜尋...........................................................................16

C.數(shù)字三角形：遞推地思索問題...........................................................17

d.石子合并：狀態(tài)的確定.................................................................17

e.街道問題：狀態(tài)量維數(shù)的確定與無后效性..................18

f.0-1背包：奇妙地選取狀態(tài)量..........................................................19

g.Bitonic旅行：最佳的狀態(tài)轉(zhuǎn)化方式...................................................20

h.最長(zhǎng)非降子序列模型...................................................................20

i.構(gòu)造動(dòng)態(tài)規(guī)劃算法...................................................................21

j.動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜尋的區(qū)分與轉(zhuǎn)化............................................21

習(xí)題....................................................................................21

6.常用數(shù)學(xué)方法...........................................22

2

a.排列組合............................................................................22

b.遞推與通項(xiàng)的選用...................................................................23

7.分治.....................................................................................26

a.子問題與母問題的相像性..............................................................26

b.二分查找.............................................................................26

C.分析算式.............................................................................26

d.最長(zhǎng)非降子序列的二分法..............................................................29

8.圖論思想................................................................................30

a.圖論基礎(chǔ).............................................................................30

b.圖的表示方法........................................................................30

C經(jīng)典圖論算法........................................................................30

d.構(gòu)造圖論模型...........................................32

習(xí)題....................................................................................33

附件：關(guān)鍵路徑算法、篝火晚會(huì)問題解法源文件...........................................33

1.模擬方法

a.用數(shù)學(xué)量和圖形描述問題

計(jì)算機(jī)處理的是數(shù)學(xué)量。若要用計(jì)算機(jī)解決實(shí)際問題，須要把實(shí)際問題抽象為數(shù)學(xué)量，或者數(shù)字。比如,

記事本把文字按ASCH碼表轉(zhuǎn)換為數(shù)字儲(chǔ)存起來，極品飛車把賽車的性能表示為數(shù)字，來權(quán)衡賽車的

好壞。一個(gè)美麗的算法，須要用數(shù)學(xué)量表示出來。

任務(wù)：現(xiàn)有兩個(gè)軟件工程的制作任務(wù)，你的團(tuán)隊(duì)可以接手其中隨意一個(gè)?，F(xiàn)要在兩個(gè)中選擇一個(gè)，須要

考慮制作成本，制作勝利的可能性，可獲得經(jīng)濟(jì)收益的多少，對(duì)你的團(tuán)隊(duì)知名度的影響等等因素。你

如何量化地分析和解決這個(gè)問題？

提示：須要把每一項(xiàng)都轉(zhuǎn)化為數(shù)值，必要時(shí)加入權(quán)值、計(jì)算期望。假如只考慮以上四個(gè)因素，可以得到

以下數(shù)學(xué)式

綜合收益二制作勝利的概率*［（可獲得經(jīng)濟(jì)收益■制作成本）*經(jīng)濟(jì)效益的權(quán)值+團(tuán)隊(duì)知名度的影響*社會(huì)

效益的權(quán)值］

其中概率和兩個(gè)權(quán)值是須要估計(jì)的值。

有時(shí)，我們須要用更直觀的圖形來描述實(shí)際問題。

圖論就是一個(gè)絕佳的方法。圖是一種表示離散量間關(guān)系的形式，它也是一種思想，常被用于建模。同時(shí),

前人也為我們供應(yīng)了很多現(xiàn)成的圖論算法，能夠解決很多常見問題，這些將在之后被提到。

矩陣也是一種常見的方法。有時(shí)矩陣被表示成三角形的形式，比如"楊輝三角"。矩陣常常和數(shù)學(xué)有關(guān),

在計(jì)算機(jī)計(jì)算時(shí)常常利用矩陣的遞推式。這也將在后面被提到。

b.模擬計(jì)算過程

模擬方法是最常見、最干脆的算法構(gòu)建方法。

任務(wù)：編程實(shí)現(xiàn)歐幾里得算法(輾轉(zhuǎn)相除法，求兩個(gè)數(shù)的最大公約數(shù)gcd(a,b))

提示：

歐幾里得算法原理：gcd(a,b)=gcd(b/amodb)

歐幾里得算法的圖形描述一

|16863||16863|2

I42|

1.寫下兩個(gè)數(shù)2.將兩數(shù)相除，余數(shù)寫在較大的數(shù)下面

|16863|2|16863|2

1|4221|1|4221|2——整除

3.將每列最下面的數(shù)相除，余數(shù)寫在被除數(shù)下面4.重復(fù)步驟3直至整除，此時(shí)最終寫下的余數(shù)即為

起先時(shí)兩數(shù)的最大公約數(shù)

這是一個(gè)簡(jiǎn)潔的模擬算法，實(shí)際過程中，量間的關(guān)系往往比這困難得多，因而，模擬算法可以是很困難

的。

有些模擬算法還涉及到圖形和其他困難的數(shù)據(jù)結(jié)構(gòu)，這須要我們嫻熟地運(yùn)用語(yǔ)言，奇妙地把其他關(guān)系轉(zhuǎn)

化為數(shù)學(xué)量間關(guān)系。

c.模擬時(shí)的優(yōu)化

假如處理不當(dāng)，模擬方法寫出的程序會(huì)特別長(zhǎng)。這要求我們?cè)谀M是將相像的步驟合為一體，適時(shí)利用

函數(shù)簡(jiǎn)化程序。

以上面的歐幾里得算法為例：

4

/*實(shí)現(xiàn)時(shí)，若將左邊一列數(shù)最下面的記為七口。0。八右邊一列數(shù)記為RM。。。］,明顯是不明智的，因

為只有每列最終一個(gè)數(shù)會(huì)在以后的計(jì)算中用到*/

/*實(shí)現(xiàn)方法一：及每一列最終一個(gè)數(shù)分別為L(zhǎng)、R.輸入即可是工、R,返回gcd伍,R)*/

intEuclid_l(intL,intR)

for(;;)

(

L=L%R;

if(L==O)returnR;

R=R%L;

if(R==O)returnL;

)

)

/峨們發(fā)覺有兩步是相像的。因而我們可以把它簡(jiǎn)化為實(shí)現(xiàn)方法二*/

intEuclid_2(intLJntR)

(

intt;

for(;;)

{

t=R;R=L%R;L=t;

if(R==0)returnL;

)

)

/*甚至我們可以寫成遞歸形式。以下是實(shí)現(xiàn)方法三?/

intEudid_3(intLJntR)

{

訐(L%R==O)returnR;

elsereturnEuclid_3(R,L%R);

)

這個(gè)實(shí)例主要體現(xiàn)模擬算法的簡(jiǎn)化過程。雖然在這樣小的程序段中，這樣的簡(jiǎn)化作用不大，但遇到困難

的模擬問題，這種利用相像性的簡(jiǎn)化便特別有用了。應(yīng)當(dāng)重視這樣的代碼優(yōu)化。

d.高精度計(jì)算算法

競(jìng)賽中常常會(huì)用上一些很大的數(shù)，超出長(zhǎng)整型的數(shù)值范圍。這時(shí)我們須要運(yùn)用高精度計(jì)算算法。這種算

法可以把數(shù)值范圍增加到我們想要的程度。

高精度函數(shù)往往包括加、減、乘、輸入、輸出五種。

實(shí)現(xiàn)高精度計(jì)算時(shí)，常常運(yùn)用模擬算法一模擬小學(xué)豎式運(yùn)算。我們把一個(gè)高精度數(shù)表示為一個(gè)數(shù)組H[],

數(shù)組中的某一個(gè)數(shù)相當(dāng)于高精度數(shù)的某一位。

要留意的是，輸出時(shí)往往要求以十進(jìn)制形式輸出。因而，高精度數(shù)每一位都應(yīng)便于干脆輸出。這樣，每

一位上的最大數(shù)都應(yīng)是10人11-1。簡(jiǎn)潔地說，若把H口定為unsigned型，高精度數(shù)每一位上最大數(shù)

最好為9999。這樣既能盡量利用儲(chǔ)存空間，又便于輸出。

另外，高精度數(shù)有時(shí)會(huì)用到負(fù)數(shù)。在補(bǔ)碼的體系中，仍舊可以按正數(shù)的方法處理負(fù)數(shù)，但是要特殊留意

輸出時(shí)的問題，和對(duì)溢出的防止。

任務(wù)：實(shí)現(xiàn)高精度運(yùn)算加法

提示：設(shè)計(jì)函數(shù)從末

unsigned*HAdd(unsignedNl[],unsignedN2[]funsignedAns[])?

位起相加，留意是否進(jìn)位。

明顯，減法作為加法的逆運(yùn)算，也很簡(jiǎn)潔實(shí)現(xiàn)。另一種聰慧的方法是，對(duì)減數(shù)每一位取補(bǔ)碼，在做加法

5

即可。請(qǐng)讀者自行實(shí)現(xiàn)高精度減法。

高精度乘法困難一些。我舉薦的方法是，先考慮多位高精度數(shù)乘一位高精度數(shù)的過程。多位高精度數(shù)乘

多位高精度數(shù)可以轉(zhuǎn)化為多位高精度數(shù)乘另一高精度數(shù)每一位，再將結(jié)果相加的過程。下面紿出多位

高精度數(shù)乘一位高精度數(shù)的源代碼：

#defineH_Bit256/*定義常數(shù)：高精度數(shù)位數(shù)*/

/*N1[J為多位高精度數(shù)

unsigned*HTimesInt(unsignedNl[],intN2runsignedAns[]),

N2為高精度數(shù)的一位，Ans〃為另一高精度數(shù)，用于儲(chǔ)存結(jié)果*/

/倉(cāng)里允許Ml與Ans相同*/

(

unsignedirup=O;

unsignedlongtemp;

(

temp=Nl[i]*N2+up;

up=temp/10000;

Ans[i]=(unsigned)(temp%10000);

}

returnAns;

/*函數(shù)返回作為答案的高精度數(shù)首地址，這樣更便于高精度運(yùn)算函數(shù)的運(yùn)用，例如連乘可以寫成

HTimesInt(HTimesInt(N1[],N2,Ans[]),N3,Ans[])*/

)

高精度數(shù)的輸入輸出須要特地的函數(shù)。針對(duì)不同語(yǔ)言的不同特點(diǎn)，可以比較簡(jiǎn)潔地寫出這兩個(gè)函數(shù)。但

要留意輸出非首位數(shù)位上的"0"。

習(xí)題

模擬方法的習(xí)題一感謝深藍(lán)評(píng)測(cè)系統(tǒng)供應(yīng)習(xí)題

6

2.排序算法與算法時(shí)空困難度

a.簡(jiǎn)潔排序算法

簡(jiǎn)潔排序算法包括冒泡排序、插入排序、選擇排序。這三種算法簡(jiǎn)潔理解、編寫便利，適用于數(shù)據(jù)規(guī)模

較小的情形。

冒泡排序(BubbleSort)的基本思路是：(以從小到大排序?yàn)槔?從前到后逐個(gè)比較相鄰兩數(shù)，若前

數(shù)大于后數(shù)，就將兩數(shù)交換。不斷重復(fù)這一過程，直至全部數(shù)字已按從小到大排好。

考慮到好用性的問題，插入排序和選擇排序這里不再介紹。

對(duì)于N0IP提高組而言，這些算法時(shí)間困難度過高，很難應(yīng)付較大的數(shù)據(jù)規(guī)模。建議盡量不要采納簡(jiǎn)潔

排序算法，除非你特別確信數(shù)據(jù)規(guī)模在可承受范圍之內(nèi)。

b.快速排序、堆排序

快速排序和堆排序是比簡(jiǎn)潔排序快的排序算法，在競(jìng)賽中常常被采納。這里，我們介紹快速排序算法。

堆排序的實(shí)現(xiàn)不作介紹，若想了解，可詢問谷歌或百度。

快速排序(Quicksort)基于分治思想。它的基本思路是：(以從小到大排序?yàn)槔?取一個(gè)數(shù)作為標(biāo)

記元素，將比它大的數(shù)放在它右側(cè)，比它小的數(shù)放在它左側(cè)，再通過遞歸的方法，將左側(cè)的數(shù)用以上

的方法排好，右側(cè)的數(shù)也用以上的方法排好即可。

下面這個(gè)視頻能很直觀地比較冒泡排序(BubbleSort)和快速排序(Quicksort)：

在數(shù)據(jù)規(guī)模很大時(shí)，平均狀況下快排比冒泡快很多。在處理N0IP提高組含排序的問題時(shí)，一般要選擇

快速排序或堆排序。

下面將介紹快速排序的實(shí)現(xiàn)(以從小到大排序?yàn)槔?。

快排運(yùn)用分治思想，因而要用函數(shù)的遞歸調(diào)用來實(shí)現(xiàn)：

voidQuickSort(inta[]rintstjntstp)//這里也可以定義成voidQuicksort(int

len).為了便于理解，我運(yùn)用前一種寫法。

(

intmid;

mid=partition(a[],stfstp);//partition。用于確定標(biāo)記元素的位置。

if(l<mid-l)QuickSort(a[]fstfmid-l);

if(mid+1<r)QuickSort(a[],mid+l,stp);

)

現(xiàn)在的關(guān)鍵問題在于如何寫partition。。

寫法一：對(duì)于數(shù)列567538162

1.取首個(gè)元素做標(biāo)記元素，取出它，令指針p指向最右邊的數(shù)的右邊

——_67538162p-

2.將p向左移動(dòng)到小于標(biāo)記元素的數(shù)(或空缺處)為止。若指向空缺，則跳到5；否則將該數(shù)和p移到

空缺處——p-26753816.

3.將p向右移動(dòng)到大于標(biāo)記元素的數(shù)(或空缺處)為止。若指向空缺，則跳到5；否則將該數(shù)和p移到

空缺處——2.753816p-6

4.重復(fù)2和3。

2p-17538.66

21.538p-766

7

21p-35_8766

5.把標(biāo)記元素放入空格處——2135p-58766

寫法二：寫法二比寫法一短一些，但理論上講，寫法二要慢一些(因?yàn)樗髻x值運(yùn)算多一些)。下面給

出源代碼與分析：

voidQuickSort(longa[],longstjongstp)//&^^partition〃結(jié)合進(jìn)QirickSor七〃

中

{

longt,nj,r;

n=a[st];

I=st+1;

r=stp;

for(;;)

{

for(;a[l]<=n&&l<=stp;l++);//從右找，找到一個(gè)小于標(biāo)記元素的數(shù)

for(;a[r]>=n&&//從左找，找到一個(gè)大于標(biāo)記元素的數(shù)

if(l>=r)break；//假如]在r右側(cè)，則跳出

t=a[l];a[l]=a[r];a[r]=t;/席換，使小于標(biāo)記元素的在左，大于標(biāo)記元素的在右

}

a[st]=a[r];//取出最右側(cè)的小于標(biāo)記元素的數(shù)寫入空缺

a[r]=n;//空缺處放入標(biāo)記元素

if(r-st>l)QuickSort(a,st,r-l);

if(stp>l)QuickSort(a,lfstp);

)

以上快排實(shí)現(xiàn)方法的最差情形是排列整齊的狀況，這時(shí)它的運(yùn)行效率會(huì)很低。為了解決排列整齊的情形,

我們可以運(yùn)用隨機(jī)快速排序法，即隨機(jī)選取一個(gè)數(shù)作為標(biāo)記元素(實(shí)現(xiàn)時(shí)，將其與第一個(gè)數(shù)交換即可)。

c.算法時(shí)空困難度

為了描述一個(gè)算法的優(yōu)劣，我們引入算法時(shí)間困難度和空間困難度的概念。

時(shí)間困難度：一個(gè)算法主要運(yùn)算的次數(shù)，用0()表示。

通常表示時(shí)間困難度時(shí)，我們只保留影響最大的項(xiàng)，并忽視該項(xiàng)的系數(shù)。

例如主要運(yùn)算為賦值的算法，賦值做了3n八3+11八2+8次，則認(rèn)為它的困難度為0(。人3)；若主要運(yùn)算為

比較，比較做了4*2An+2*nA4+700次，由于數(shù)據(jù)很大時(shí)，指數(shù)級(jí)增長(zhǎng)的2人11影響最大，我們認(rèn)為它

的時(shí)間困難度為0(2人口)。

常見的時(shí)間困難度有下列幾個(gè)：

0(n)—貪心算法多數(shù)狀況下為此時(shí)間困難度

O(nlbn)—有時(shí)帶有分治思想的算法的時(shí)間困難度(注Ibn表示以2為底的n的對(duì)數(shù))

0(nA2)—有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間困難度

O(nA3)——有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間困難度

0(2八n)—有時(shí)搜尋算法的時(shí)間困難度

0(n!)一有時(shí)搜尋算法的時(shí)間困難度

有時(shí)時(shí)間困難度中含有兩個(gè)或多個(gè)字母，比如遍歷一個(gè)m*n的矩陣，時(shí)間困難度為

要留意的是，時(shí)間困難度相同的兩個(gè)算法，它的實(shí)際執(zhí)行時(shí)間可能會(huì)有數(shù)倍的差距，因而實(shí)現(xiàn)時(shí)要特殊

留意細(xì)微環(huán)節(jié)處的優(yōu)化。

8

NOIP提高組執(zhí)行時(shí)限常常為1s.一般認(rèn)為，將數(shù)據(jù)規(guī)模代入到時(shí)間困難度，若所得值小于或接近于

1000000,就是確定平安的、不超時(shí)的。

例如，0(。人2)的動(dòng)態(tài)規(guī)劃算法，可承受的數(shù)據(jù)規(guī)模是nw1000；0(2人n)的搜尋算法，可承受的數(shù)據(jù)規(guī)

模是nw20；O(n!)的搜尋算法，可承受的數(shù)據(jù)規(guī)模是nw9。

事實(shí)上，以現(xiàn)在的CPU運(yùn)行速度，5000000也應(yīng)當(dāng)不成問題。

空間困難度：一個(gè)算法消耗儲(chǔ)存空間(內(nèi)存)的大小，用0()表示。

空間困難度的表示規(guī)則與時(shí)間困難度類似。

在實(shí)際應(yīng)用時(shí)，空間的占用是須要特殊留意的問題。太大的數(shù)組常常是開不出來的，即使開出來了，遍

歷的時(shí)間消耗也是驚人的。

下面我們簡(jiǎn)潔地分析一下簡(jiǎn)潔排序算法、快速排序、堆排序的時(shí)空困難度。

這三種算法都是基于比較的排序算法，以比較次數(shù)作為主要運(yùn)算。

簡(jiǎn)潔排序算法最差時(shí)需做11人2次比較，平均狀況下時(shí)間困難度通常被認(rèn)為是O(n八2)。

快速排序最差時(shí)需做|1人2次比較，可以證明平均狀況下需做Mbn次比較，時(shí)間困難度是O(nlbn).

堆排序時(shí)間困難度是O(Zbn)。

空間上，三者都不須要額外開拓暫存數(shù)組，快排遞歸調(diào)用時(shí)須要運(yùn)用稍多一些的儲(chǔ)存空間。

綜合來看，快速排序、堆排序優(yōu)于簡(jiǎn)潔排序算法。

另外，可以證明基于比較的排序算法時(shí)間困難度下界為O(nlbn)。

d.時(shí)空的簡(jiǎn)潔優(yōu)化方法

時(shí)間上的優(yōu)化在于少做運(yùn)算、做耗時(shí)短的運(yùn)算等。

有幾個(gè)規(guī)律須要留意：

整型運(yùn)算耗時(shí)遠(yuǎn)低于實(shí)型運(yùn)算耗時(shí)。

+、?運(yùn)算特別快(減法是將減數(shù)取補(bǔ)碼后與被減數(shù)相加，其中位運(yùn)算更快一些，但是減法也比加法稍

慢些。)

*運(yùn)算比加法慢得多

/運(yùn)算比乘法慢得多

比較運(yùn)算慢于四則運(yùn)算

賦值運(yùn)算慢于比較運(yùn)算(因?yàn)橐獙憙?nèi)存)

這些規(guī)律我們可以從宏觀上把握。事實(shí)上，原委做了幾步運(yùn)算、幾次賦值、變量在內(nèi)存還是緩存等多數(shù)

由編譯器、系統(tǒng)確定。

但是，少做運(yùn)算(尤其在循環(huán)體、遞歸體中)確定能很大程度節(jié)約時(shí)間。

下面來舉一個(gè)例子：計(jì)算組合數(shù)C(m,n)—n件物品取出m件的組合數(shù)。

C(m,n)可用公式干脆計(jì)算。C(m,n)=n!/((n-m)!m!),C(m,n)=n(n-l)(n-2)...(n-m+l)/(n-m)!o

明顯，有時(shí)所作的乘法少很多，會(huì)快一些。

可是這樣算真的最快嗎？

另一條思路是C(m,n)=遞推下去，直到可利用CQ,k)=k=C(k?l,k)為止。

我覺得這種只用加法的運(yùn)算會(huì)快些，盡管加法多一些。(我沒試驗(yàn)過，你可以去試一下。)

空間上的優(yōu)化主要在于減小數(shù)組大小、降低數(shù)組維數(shù)等。

常用的節(jié)約內(nèi)存的方法有：

壓縮儲(chǔ)存——例：數(shù)組中每個(gè)數(shù)都只有0、1兩種可能，則可以按位儲(chǔ)存，空間壓縮為原來的八分之一。

覆蓋舊數(shù)據(jù)一例：矩陣中每一行的值只與上一行有關(guān)，輸出只和最末行有關(guān)，則可將奇數(shù)行儲(chǔ)存在第一

行，偶數(shù)行儲(chǔ)存在其次行，降低空間困難度。

要留意的是，對(duì)空間的優(yōu)化即使不變更困難度、只是變更n的系數(shù)也是極有意義的?？臻g困難度有時(shí)對(duì)

時(shí)間也有影響，要想方設(shè)法進(jìn)行優(yōu)化。

e.線性時(shí)間排序

基于比較的排序算法時(shí)間困難度下界為O(nlbn).因而，若還要降低困難度，要放棄基于比較的排序

9

算法。

有一類排序算法叫做線性時(shí)間排序，它們的時(shí)間困難度為O(n)。下面介紹一種。

計(jì)數(shù)排序思路：開拓暫存數(shù)組b口，b[k]表示欲排序數(shù)組a口中k出現(xiàn)的次數(shù)(須要遍歷a口)，最終

遍歷b口，可將a口排好。

這種想法特別簡(jiǎn)潔，實(shí)現(xiàn)也很簡(jiǎn)潔。事實(shí)證明，在a口取值范圍很?。ㄈ缯头秶r(shí)，它是很高效的

排序算法，比快排快不少?？墒莂口取值范圍較大（如長(zhǎng)整型范圍）時(shí)，它的執(zhí)行時(shí)間會(huì)變長(zhǎng)，而且

數(shù)組b口有時(shí)開不出來。

事實(shí)上計(jì)數(shù)排序時(shí)間困難度為O（n+m）,空間困難度也為O（n+m）,m表示a口取值范圍。若m很大，

則也不能在時(shí)限內(nèi)執(zhí)行完。

￡.歸并排序

有一種排序時(shí)極為常見的情形：有一張成果表，記錄著很多學(xué)生的成果，要將他們按成果排序，但成果

相同者的相對(duì)依次不能變更。

換句話說，ABCDE五人，A、C、D成果相同，明顯排序完之后會(huì)排在一起，現(xiàn)在的要求是：他們排在

起的依次也必需是ACD,不能是ADC、CAD...

這樣的實(shí)際問題涉及到排序的穩(wěn)定性。

排序的穩(wěn)定性：一個(gè)排序算法，若可使排序前后關(guān)鍵字相同的項(xiàng)相對(duì)依次不變，則稱該排序算法是穩(wěn)定

的排序算法。

下面我們來考察常見排序算法的穩(wěn)定性。

在編寫合理的狀況下，簡(jiǎn)潔排序算法是穩(wěn)定的；快速排序、堆排序是不穩(wěn)定的（你可以好好想想這是為

什么）。

在NOIP中，往往排序是沒有附帶其他項(xiàng)目的，也就不要求排序穩(wěn)定?？焖倥判?、堆排序仍舊是最佳選

擇。

可是有沒有時(shí)間困難度為O（nlbn）的穩(wěn)定的排序算法呢？有的。

歸并排序基于分治思想：把要排序的數(shù)組平分兩半，對(duì)兩部分分別排序（遞歸地）后再合并起來。合并

時(shí)，將一個(gè)數(shù)組按依次插入另一個(gè)數(shù)組中，須要開拓一個(gè)暫存數(shù)組。利用空間優(yōu)化，可只用開拓一個(gè)

與原數(shù)組等大的數(shù)組。

歸并排序的源代碼會(huì)放在本章的附件中。請(qǐng)讀者自己探討。

歸并排序的優(yōu)缺點(diǎn)都很明顯。無論情形如何，它的比較次數(shù)、賦值次數(shù)都穩(wěn)定在nlbn,沒有最差狀況，

運(yùn)行時(shí)間與快速排序、堆排序相當(dāng)。而且，它是穩(wěn)定的排序算法。

但是，它的內(nèi)存占用回達(dá)到快速排序、堆排序的兩倍，競(jìng)賽時(shí)運(yùn)用簡(jiǎn)潔造成內(nèi)存超出限制。

NOIP初賽曾考察過歸并排序。問題大意是：找出一個(gè)算法，使五個(gè)數(shù)在n次比較（兩兩比較）后確定

能排定次序，求n的最小值。

在快速排序、堆排序的最差狀況下，須要10次、9次比較。可是，運(yùn)用歸并排序只須要7次！汜住：歸并

排序沒有最差狀況。

g.合理選用排序算法

下面是本章講過的排序算法的優(yōu)缺點(diǎn)比較：(這里只講最主要的)

排序算法時(shí)間困難度優(yōu)點(diǎn)缺點(diǎn)

簡(jiǎn)潔排序0m八2)編寫便利執(zhí)行時(shí)間長(zhǎng)

快排O(nlbn)執(zhí)行時(shí)間短很差狀況下執(zhí)行時(shí)間長(zhǎng)、占用內(nèi)存多

堆排序O(nlbn)執(zhí)行時(shí)間短編寫有點(diǎn)麻煩，有較差的狀況

計(jì)數(shù)排序O(n+m)編寫便利，取值范圍小時(shí)很高效取值范圍大時(shí)效率低、易超內(nèi)存限制

歸并排序O(nlbn)穩(wěn)定的排序算法，無較差狀況占用內(nèi)存很大

競(jìng)賽中首選快速排序、堆排序。但有時(shí)也應(yīng)比較各排序的優(yōu)缺點(diǎn)，依實(shí)際合理選用。

習(xí)題

排序的習(xí)題一感謝深藍(lán)評(píng)測(cè)系統(tǒng)供應(yīng)習(xí)題

10

3.搜尋

a.困難的模擬問題與利用相像性

在講模擬方法時(shí)我們講過利用相像性來簡(jiǎn)化算法?，F(xiàn)在，我們接著關(guān)注這個(gè)問題。

搜尋算法是一種"模擬"思維的算法，比較接近平常的思維。與模擬算法相比，它更深刻地利用了相像性。

為了更好地說明，下面舉一個(gè)例子：

有一把有n位字母的密碼鎖，每一位上的字母都可從a到Z選取?，F(xiàn)密碼被遺忘，開鎖時(shí)，請(qǐng)給出一個(gè)

便利的方法，使每個(gè)字母組合都被嘗試過。

最簡(jiǎn)潔想到J的方法便是，按aa…aa，aa...ab,aa...ac,...?aa...az,aa…ba，...?zz...zy,zz...zz這

樣

的字典序來嘗試。

我們可以這樣考慮：

先選定第一位，再選定其次位，……，直到選定第n位，形成一個(gè)完整的字母組合。

具體地，在每一位的選取時(shí)，都從a起先，到后面位的字母組合全部嘗試過，再跳到下一個(gè)字母：若(非

首位)己經(jīng)跳到z而還需再跳一個(gè)字母時(shí)，就跳到a,同時(shí)讓它的前一位跳到下一個(gè)字母。

例如，n=3時(shí)，形成的字母組合的依次是

aaa-aaa

b-aab

c-aac

z-aaz

ba-aba

b-abb

???

z-abz

ca-aca

??????

zz-azz

baa-baa

??????

zz-bzz

caa-caa

zzz-zzz

以上描述的是一種常見的遍歷方法。

我們留意到，選定每一位的過程是極其相像的。我們須要利用這種相像性。

b.函數(shù)的遞歸調(diào)用

結(jié)構(gòu)化編程語(yǔ)言供應(yīng)的最大好處無疑是函數(shù)的遞歸調(diào)用。

假如把函數(shù)看成解決某個(gè)問題的過程，那么遞歸就可以看成把問題變成相像而更小的問題的過程。留意

這兩個(gè)關(guān)鍵詞：相像、更小。遞歸的本質(zhì)是利用相像性。

我們接著講上面提到的密碼鎖問題?，F(xiàn)在我們要把嘗試過的字母組合都輸出到屏幕上。

我們用遞歸法來完成這個(gè)過程。寫遞歸體一般分為兩步：把大問題化成小問題、解決最小問題。

charstring[1000],n;

voidcode(intLeft)//遞歸體，Left表示還須要確定的位數(shù)，這個(gè)值隨問題的減小而遞減。

11

if（Left>=l）/力巴大問題化成小問題

for(string[n-Left]="a';string[n-Left]<='z';string[n-Left]++)

code(Left-l);

if（Left==0）//解決最小問題

printf("%s\n",stnng);

)

intmain()

fscanf("%d"f&n);

string[n]='\0';

code(n);

return0;

)

分析這個(gè)方法，得知其時(shí)間困難度為0（26八n）。

補(bǔ)充一句，上面的過程也可用n個(gè)for的嵌套來實(shí)現(xiàn)（你能做到嗎？）。

c.我與深度優(yōu)先搜尋

搜尋分為深度優(yōu)先搜尋、廣度優(yōu)先搜尋兩種。下面用樹區(qū)分這兩種搜尋方法。

對(duì)于樹，從根節(jié)點(diǎn)起先,查找（遍歷）各節(jié)點(diǎn)，分兩種方式：

從某一節(jié)點(diǎn)向下擴(kuò)展時(shí),若先遍歷其子節(jié)點(diǎn)，再查找其子節(jié)點(diǎn)的子節(jié)點(diǎn)一廣度優(yōu)先搜尋。

從某一節(jié)點(diǎn)向下擴(kuò)展時(shí),若遇到子節(jié)點(diǎn)就“深化”到子節(jié)點(diǎn)的子節(jié)點(diǎn)，直到葉子節(jié)點(diǎn)再返回一深度優(yōu)先

搜

索。

對(duì)于7頂點(diǎn)的完全二叉樹，兩種方式所到達(dá)的頂點(diǎn)依次如下:

11

2325

45673467

廣度優(yōu)先深度優(yōu)先

留意：搜尋面對(duì)的數(shù)據(jù)結(jié)構(gòu)往往不是樹。

明顯，深度優(yōu)先搜尋的擴(kuò)展方式類似于上面敘述的函數(shù)遞歸。這里，我們先分析它。

深度優(yōu)先搜尋在實(shí)現(xiàn)時(shí)有兩種方式：遞歸形式、非遞歸形式。

遞歸形式利用一個(gè)函數(shù)(以整型為例)intcal(...)：

intcal(...)

{

intn;

〃運(yùn)算

n=cal(…);〃遞歸，常在循環(huán)體中

〃運(yùn)算

returnn;〃返回

)

非遞歸形式利用一個(gè)棧，它可以被看作是遞歸形式的一個(gè)變更：

當(dāng)要遞歸地調(diào)用cal(…)時(shí)，不馬上調(diào)用cal(…)，而是將其參數(shù)壓入棧。等函數(shù)運(yùn)行完，再?gòu)臈Ｖ袕?/p>

出其參數(shù)并再次執(zhí)行函數(shù)cal(…)。

這樣，最終被調(diào)用的最先執(zhí)行。由于后查找的是深度最大的，這樣的結(jié)果是深度優(yōu)先。

深度優(yōu)先搜尋往往采納遞歸方法。

12

一代算法宗師迪杰斯特拉(E.W.Dijkstra)極力推崇遞歸法。它編寫便利、清晰，只是內(nèi)存消耗略

比非遞歸大。非遞歸法往往在擔(dān)憂內(nèi)存溢出時(shí)運(yùn)用。

深度優(yōu)先搜尋的巨大優(yōu)勢(shì)就是可以領(lǐng)先到達(dá)葉子節(jié)點(diǎn)。對(duì)于“找出一種方法"、"找出其中一個(gè)解”這樣

的

問題有速度上的優(yōu)勢(shì)。這里舉例分析。

八數(shù)碼問題；九宮格里有八個(gè)分力J填上了數(shù)字1-8,形成最初構(gòu)型。每步只能把空格上下左右的數(shù)之一

與空格對(duì)調(diào)?，F(xiàn)要求找出一種方法，使若干步對(duì)調(diào)后呈現(xiàn)目標(biāo)構(gòu)型。例如:

572123

4_1->456

63878_

思路：每次將一個(gè)構(gòu)型變?yōu)榱硪粋€(gè)，再遞歸地檢查后者能否到達(dá)目標(biāo)構(gòu)型。時(shí)間困難度0（4人n）。

偽代碼：

intEightNumbers（構(gòu)型）這里返回步驟數(shù)，若須要知道具體步驟，則用另用棧儲(chǔ)存步驟。

{

同源構(gòu)型則返回32767

同目標(biāo)構(gòu)型則返回0

n[l]=EightNumbers（變更出的構(gòu)型1）

n[2]=EightNumbers（變更出的構(gòu)型2）

n[3]=EightNumbers（變更出的構(gòu)型3）

n[4]=EightNumbers（變更出的構(gòu)型4）

step=最小值

step為32767貝1返1回32767

返回step+1

}

d.深度優(yōu)先搜尋的優(yōu)化

明顯，以上代碼是可以優(yōu)化的。深搜的優(yōu)化過程也叫"剪枝"?？紤]到好用性，這里我們只講最簡(jiǎn)潔的剪

枝方法。

對(duì)于上面的偽代碼，將“同源構(gòu)型則返回32767"改為"同己查找構(gòu)型則返回32767”就可以顯著提高效

率。

但是這里須要開拓一個(gè)數(shù)組（棧），記錄之前“經(jīng)過”的構(gòu)型。假如想避開遍歷數(shù)組，可以做成哈希表,

而且要壓縮儲(chǔ)存才行。

還有的簡(jiǎn)潔方法，編寫的時(shí)候自然會(huì)想到的。關(guān)鍵是要權(quán)衡，用這樣的方法所增加的編寫難度是否配得

上所節(jié)約的運(yùn)行時(shí)間。編寫難度增大，調(diào)試的難度也會(huì)增大哦。

e.隊(duì)列與廣度優(yōu)先搜尋

上面講過用棧來非遞歸地實(shí)現(xiàn)深搜。若是把棧改成隊(duì)列呢？

經(jīng)過分析，你會(huì)發(fā)覺，這樣修改后深搜變成了廣搜！

用這樣的方法可以實(shí)現(xiàn)廣搜。

用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)避開大量元素的移動(dòng)。實(shí)現(xiàn)時(shí)，可以先算出隊(duì)列元素的上限max,開拓a[max],并

設(shè)a[st]為隊(duì)列起始(st初值為0),隊(duì)列的第i項(xiàng)儲(chǔ)存在a[(st+i-l)%max]。

這樣，出隊(duì)列只用將st=(++st%max)即可。

要留意的問題是，廣搜類似于遞推，往往須要開拓空間儲(chǔ)存每一步“遞推"所得到的值。

f.廣度優(yōu)先搜尋的優(yōu)化

廣度優(yōu)先搜尋比較簡(jiǎn)潔優(yōu)化，運(yùn)行時(shí)間往往比深搜短一些(不過內(nèi)存占用比深搜大得多)。另外，廣搜

有時(shí)可以清晰地反映搜尋深度。

若上面的八數(shù)碼問題改為“現(xiàn)要求找出一種方法，使呈現(xiàn)目標(biāo)構(gòu)型經(jīng)過的對(duì)調(diào)步數(shù)最少”，則用廣搜更好。

13

廣搜常用的優(yōu)化方法：

哈希表法一記錄隊(duì)列中已有節(jié)點(diǎn)，用于推斷是否須要擴(kuò)展節(jié)點(diǎn)。

A*算法一構(gòu)造估價(jià)函數(shù)。

雙向廣度優(yōu)先搜尋——從源節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)一起起先搜尋。

由于NOIP提高組近年來幾乎不出搜尋題；可用搜尋的題目，由于搜尋時(shí)間困難度太高，數(shù)據(jù)規(guī)模太大，

搜尋只能得部分分?jǐn)?shù)。加之搜尋思路較簡(jiǎn)潔，搜尋法這里不再具體敘述。若想了解，大家可以用搜尋

引擎搜尋。

習(xí)題

搜尋的習(xí)題一感謝深藍(lán)評(píng)測(cè)系統(tǒng)供應(yīng)習(xí)題

14

4.貪心方法

a.工程支配模型

我們常常遇到這樣的問題：完成一個(gè)工程須要若干個(gè)步驟，每個(gè)步驟都有若干種方法，圖示一

步驟a步驟b步驟c…步驟n

方法bl方法cl

方法al方法b2方法c2方法nl

方法a2方法b3方法c3

方法c4

每個(gè)方法有一個(gè)權(quán)值（如效率、質(zhì)量），其大小往往和其他步驟中選取的方法有關(guān)。有些時(shí)候權(quán)值無意

義，表示方法不行選擇。要求給出一個(gè)方法組合，是權(quán)值和最大。

在這里，暫且把它稱作“工程支配"。很多實(shí)際問題都可以歸納為這個(gè)模型。

對(duì)于不同形式的工程支配，我們有不同的解法。

若權(quán)值與整個(gè)過程或前后步驟的方法選擇都有關(guān)，我們運(yùn)用搜尋算法一時(shí)間困難度高得嚇人。

若每個(gè)權(quán)值只與上（或下）一步或少數(shù)幾步的方法選擇都有關(guān)，我們運(yùn)用動(dòng)態(tài)規(guī)劃一有比較高的效率，

在下一章會(huì)講到。

若每個(gè)權(quán)值與其他步驟的方法選擇都沒有關(guān)系，我們運(yùn)用貪心方法。

b.部分背包與每步最優(yōu)

強(qiáng)調(diào)：每個(gè)權(quán)值與其他步驟的方法選擇都沒有關(guān)系。這樣每步最優(yōu)就可以得到全局最優(yōu)一每一步都取最

大的權(quán)值就可以了。

換而言之，貪心算法要求，局部的貪心選擇，可以組成全局的最優(yōu)解。

在實(shí)際問題中，這是須要證明的。假如這個(gè)無法證明，貪心算法所得的解不是最優(yōu)解，一般只是較優(yōu)解

（較優(yōu)解可為搜尋剪枝供應(yīng)便利）。

下面是貪心算法最經(jīng)典的例子：部分背包問題。（下一章會(huì)講到另外兩種背包問題。）

問題：有N件物品和一個(gè)最大載重為M的背包，每件物品都有相應(yīng)的重量和價(jià)值?，F(xiàn)要求給出一個(gè)存放

方案，使背包中物品總價(jià)值最大。部分背包要求，每件物品都可只裝入它的一部分（部分重量有成比

例的部分價(jià)值）。所涉及到的數(shù)字均為整數(shù)。

（注：有時(shí)該問題表述為體積形式，即背包體積有限，每件物品有體積和價(jià)值。在本系列我選擇表述為

重量形式。）

思路：背包中物品總價(jià)值最高，即單位重量物品價(jià)值最高。明顯，應(yīng)當(dāng)多裝單位重量?jī)r(jià)值高的物品。這

樣，我們先裝入單位重量?jī)r(jià)值最高的物品，再裝入其次高的……直到重量達(dá)到M（有必要時(shí)最終一件物

品只裝一部分），己達(dá)到物品總價(jià)值最高。

這個(gè)證明應(yīng)當(dāng)很嚴(yán)謹(jǐn)吧?

該算法時(shí)間困難度0（n）,效率很高；而且實(shí)現(xiàn)很簡(jiǎn)潔。這些是貪心法最大的特點(diǎn)。

很多競(jìng)賽題看似可以用貪心法，其實(shí)貪心法得不到最優(yōu)解，緣由是每一步的選擇對(duì)其他步驟有影響。

數(shù)字三角形問題：有一個(gè)數(shù)字三角形（如下圖）。現(xiàn)有一只螞蟻從頂層起先向下走，每走下一級(jí)時(shí)，可

向左下方向或右下方向走。求走究竟層后它所經(jīng)過的數(shù)的最大值。

1

63

826

2165

32476

假如用貪心法，每次向最大的方向走，得到結(jié)果為1+6+8+2+3=20?？墒敲髅鬟€有另一條路，

1+3+6+6+7=23。

15

問題出在哪？每次的選擇對(duì)后面的步驟會(huì)有影響！第三級(jí)選了8,就選不到第四、五級(jí)較大的數(shù)了。

這個(gè)問題正確的解法會(huì)在下一章介紹。

有一個(gè)很好用的小技巧：競(jìng)賽題會(huì)給出數(shù)據(jù)規(guī)模。通過數(shù)據(jù)規(guī)模，我們可以大致推斷該用何種算法。貪

心算法可承受的數(shù)據(jù)規(guī)模很大，一般都會(huì)上萬。假如給出的數(shù)據(jù)規(guī)模是100或1000,優(yōu)先考慮動(dòng)態(tài)規(guī)

劃吧。

c.構(gòu)造貪心算法

構(gòu)造與證明是貪心算法的難點(diǎn)，常常要求我們要有敏銳的視察力、多角度思索的變通實(shí)力、豐富的數(shù)學(xué)

學(xué)問和推理實(shí)力。

下面舉幾個(gè)貪心算法的例子，供大家揣摩、駕馭規(guī)律。

刪數(shù)問題：給出一個(gè)N位的十進(jìn)制高精度數(shù)，要求從中刪掉S個(gè)數(shù)字（其余數(shù)字相對(duì)位置不得變更），

使剩余數(shù)字組成的數(shù)最小。

算法構(gòu)造：

1.每次找出最靠前的這樣的一對(duì)數(shù)字一兩個(gè)數(shù)字緊鄰，且前面的數(shù)字大于后面的。刪除這對(duì)數(shù)字中靠前

的一個(gè)。

2.重復(fù)步驟1,直至刪去了S個(gè)數(shù)字或找不到這樣的一對(duì)數(shù)。

3.若還未刪夠S個(gè)數(shù)字，則舍棄末尾的部分?jǐn)?shù)字，取前N?S個(gè)。

證明思路：明顯，在只刪一個(gè)數(shù)字時(shí)，唯有步驟1的方法能使數(shù)變??；可推理得出，刪多個(gè)數(shù)字時(shí)，所

有最優(yōu)的方法都可看做是對(duì)步驟1的重復(fù)。也就是說，以上方法是最優(yōu)策略之一。

在文末的附件中給出了這個(gè)算法的源代碼。

工序問題：n件物品，每件需依次在A、B機(jī)床上加工。已知第i件在A、B所需加工時(shí)間分別為A[i]、

B[ib設(shè)計(jì)一加工依次，使所需加工總時(shí)間最短。

算法構(gòu)造：

1.設(shè)置集合F、M、S；先加工F中的，再加工M中的，最終加工S中的。

2.對(duì)第i件，若A[i]B[i],則歸入S；若A[i]=B[i],則歸入M。

3.對(duì)F中的元素按A[i]升序排列，S中的按B[i]降序排列。

證明思路：

1.F中的能“拉開"A、B加工同一件工件的結(jié)束時(shí)刻，為后面的工件加工“拉開時(shí)間差”，利于節(jié)約總

時(shí)

間。S中的剛好相反。因而，F(xiàn)中元素放在最前確定是最優(yōu)策略之一。

2.F中A川小的前置，可以縮短起先時(shí)B的空閑時(shí)間，但會(huì)使F全部工件”拉開的時(shí)間差”縮短。不過

可以證明，后者帶來的損失不大于前者獲得的優(yōu)勢(shì)。對(duì)稱地，對(duì)S也一樣。因而步驟3是可行的。

種樹問題：一條街道分為n個(gè)區(qū)域（按l-n編號(hào)），每個(gè)都可種一棵樹。有m戶居民，每戶會(huì)要求在區(qū)

域i?j區(qū)間內(nèi)種至少一棵樹?，F(xiàn)求一個(gè)能滿意全部要求且種樹最少的方案。

算法構(gòu)造：

1.對(duì)于要求，以區(qū)間右端（升序）為首要關(guān)鍵字，左端（升序）為次要關(guān)鍵字排序。

2.按排好的序依次考察這些要求，若未滿意，則在其最右端的區(qū)域種樹，這時(shí)可能會(huì)滿意多個(gè)要求。

證明思路：解法并不唯一，關(guān)鍵是證明沒有比該解法更好的解法。按步驟1排序之后，會(huì)發(fā)覺對(duì)于每個(gè)

要求，在最右邊的區(qū)域內(nèi)種樹所得的結(jié)果總不會(huì)差于在其他區(qū)域種樹。至于為什么這樣排序，留給你

—讀者們思索吧。

在文末的附件中給出了這個(gè)算法的源代碼。

習(xí)題

貪心方法的習(xí)題一感謝深藍(lán)評(píng)測(cè)系統(tǒng)供應(yīng)習(xí)題

16

5.動(dòng)態(tài)規(guī)劃

a.另一種形式的工程支配

b.記憶化搜尋

c.數(shù)字三角形：遞推地思索問題

d.石子合并：狀態(tài)的確定

e.街道問題；狀態(tài)量維數(shù)的確定與無后效性

f.o-l背包：奇妙地選取狀態(tài)量

g.Bitonic旅行：最佳的狀態(tài)轉(zhuǎn)化方式

h.最長(zhǎng)非降子序列模型

i.構(gòu)造動(dòng)態(tài)規(guī)劃算法

j.動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜尋的區(qū)分與轉(zhuǎn)化

a.另一種形式的工程支配

上一章我們講過，若工程支配問題中某一步權(quán)值只和上一步或少數(shù)幾步的選擇有關(guān)，我們可以運(yùn)用效率

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

看下面這個(gè)問題：

4-9

/\

1-2-5-3-1

\\//

1-7-8

上圖的數(shù)字間連了線。現(xiàn)要從最左邊的"1"走到最右邊的“1"，每次都只能沿線向右走到右邊一列的某

個(gè)數(shù)上，要求找出一條路徑，路徑上的五個(gè)數(shù)之和最大。

當(dāng)然我們可以把這理解為工程支配問題的一種形式。

這里，每一步的選擇與上一步相關(guān)；好像也與前面幾步的選擇有關(guān)，但是留意，前幾步的影響都可以表

現(xiàn)在上一步上，上一步方法的選擇已經(jīng)可以獨(dú)立確定這一步每種選擇的權(quán)值。此處適用動(dòng)態(tài)規(guī)劃。

換句"專業(yè)”點(diǎn)的話，這里滿意“無后效性原則”，即之后過程不受之前具體過程的影響。這在后面會(huì)具

體

說明。

b.記憶化搜尋

再講動(dòng)態(tài)規(guī)劃之前，我們先接觸一下記憶化搜尋。

留意到，在深度優(yōu)先搜尋中，用于遞歸的函數(shù)cal(…)有時(shí)會(huì)被用同樣的參數(shù)調(diào)用多次。你可能很簡(jiǎn)潔

想到，假如在第一次調(diào)用時(shí)把參數(shù)和對(duì)應(yīng)的函數(shù)值儲(chǔ)存起來，若以后再以同樣的參數(shù)調(diào)用，就不用執(zhí)

行遞歸函數(shù)，干脆取出所得的值，不是快得多？

假如你能想到這些，你就已經(jīng)學(xué)會(huì)記憶化搜尋了。

事實(shí)上，記憶化搜尋能大幅提高效率的地方，往往是在動(dòng)態(tài)規(guī)劃的題目中。

動(dòng)態(tài)規(guī)劃能解決的問題，往往可以用記憶化搜尋替代動(dòng)態(tài)規(guī)劃解決。假如你實(shí)在無法駕馭動(dòng)態(tài)規(guī)劃，你

可以選擇運(yùn)用記憶化搜尋。不過你要留意以下事實(shí)：

動(dòng)態(tài)規(guī)劃程序?qū)崿F(xiàn)較簡(jiǎn)潔，程序段短，便于調(diào)試；記憶化搜尋實(shí)現(xiàn)就比較繁瑣。

雖然記憶化搜尋可以把時(shí)間困難度降低到動(dòng)態(tài)規(guī)劃的水平，但是實(shí)際執(zhí)行時(shí)間會(huì)大于動(dòng)態(tài)規(guī)劃，甚至有

幾倍到十幾倍的差距。

這里不給出記憶化搜尋的代碼了。我們還是首選動(dòng)態(tài)規(guī)劃吧?

17

c.數(shù)字三角形：遞推地思索問題

上一章中我們講過數(shù)字三角形問題：

有一個(gè)數(shù)字三角形（如下圖）。現(xiàn)有一只螞蟻從頂層起先向下走，每走下一級(jí)時(shí)，可向左下方向或右下

方向走。求走究竟層后它所經(jīng)過的數(shù)的最大值。

1

63

826

2165

32476

對(duì)于這個(gè)問題，貪心法得不到最優(yōu)解，搜尋法效率太低。我們知道，深度優(yōu)先搜尋利用了遞歸式的思維，

動(dòng)態(tài)規(guī)劃中，我們運(yùn)用遞推式的思維。

遞歸：要知道第五層時(shí)的最大值，就要知道第四層時(shí)的最大值；要知道第四層時(shí)的最大值，就要知道第

三層時(shí)的最大值……而每一步推導(dǎo)的方法是相像的。

遞推：知道第一層的最大值，就能知道其次層的最大值，也就能知道第三層的最大值……而每一步推導(dǎo)的

方法是相像的。

對(duì)比之下，遞推思維不是從結(jié)論入手的，有時(shí)簡(jiǎn)潔失去方向；但是有時(shí)卻可以有很高的效率。

動(dòng)態(tài)規(guī)劃和一般遞推的區(qū)分在于動(dòng)態(tài)規(guī)劃須要在每一步作比較、取最優(yōu)值。

對(duì)于數(shù)字三角形問題，我們可以這樣思索：設(shè)二維數(shù)組表示走到第i行的第j個(gè)數(shù)時(shí)所經(jīng)

過的數(shù)字和的最大值。例如對(duì)圖中三角形，A[3][2]=max{l+6+2,l+3+2}o

這樣，我們又可以得到遞推關(guān)系A(chǔ)[i]m=p[i]U]+max{A[i?l]rl],A[i?l]m}（實(shí)現(xiàn)時(shí)注

意或不存在時(shí)的處理），其中表示第i行的第j個(gè)數(shù)的數(shù)值。

此外，我們還須要一些初始值：p[i][jl（輸入），A[l][l]=p[l][l]o

最終我們可以求出A[5][j],結(jié)論自然是max{A[5]皿}啦?

分析這個(gè)算法，若層數(shù)大于5,則時(shí)間困難度為O（n人2）。若用搜尋，時(shí)間困難度為0（2八11）。明顯動(dòng)態(tài)

規(guī)劃效率高很多。

為了更清晰地說明動(dòng)態(tài)規(guī)劃算法，我們先引入一些概念。

階段一我們把問題劃分為幾步，在動(dòng)態(tài)規(guī)劃中，這叫做"劃分階段"。數(shù)字三角形中，每一層可看作是

個(gè)階段。

狀態(tài)一每一階段有多種選擇，不同的選擇會(huì)有不同的結(jié)果，我們把每階段的不憐憫形叫做“狀態(tài)"。每

階段包括多個(gè)狀態(tài)。數(shù)字三角形中，表示走到第j個(gè)數(shù)時(shí)所經(jīng)過的數(shù)字和的最大值的變量叫做狀態(tài)。

動(dòng)態(tài)轉(zhuǎn)移方程一我們可以用一個(gè)遞推式表示某階段到下一階段的遞推關(guān)系，這個(gè)遞推式叫做動(dòng)態(tài)轉(zhuǎn)移方

程。動(dòng)態(tài)轉(zhuǎn)移方程一般含有max?；騧in{}。

決策一即對(duì)方法的選擇。每個(gè)階段都有一個(gè)決策。這樣的選擇是有范圍的，這個(gè)范圍叫做“決策允許集

合”。

策略一一套完整的決策的組合。“最優(yōu)策略”即最佳的決策組成的策略。

還有一些概念因?yàn)檫\(yùn)用較少，這里不再具體介紹。

留意可以運(yùn)用動(dòng)態(tài)規(guī)劃解決的問題的兩個(gè)必需特性：

最優(yōu)化原理一簡(jiǎn)潔地說，最優(yōu)策略某幾個(gè)連續(xù)階段上的決策組合，也是這幾個(gè)階段組成的子問題的最優(yōu)

策略。

無后效性原則一某階段以后的決策，與該階段之前的具體決策無關(guān)，只與該階段的狀態(tài)有關(guān)。

留意，有些時(shí)候我們認(rèn)為不滿意這兩點(diǎn)的問題，換個(gè)角度看又是滿意的。這正是動(dòng)態(tài)規(guī)劃的4點(diǎn)。接下

來我們就是要找尋合適的角度，找出滿意這兩個(gè)關(guān)系的算法。

d.石子合并：狀態(tài)的確定

用動(dòng)態(tài)規(guī)劃解決問題，首要也是最重要的步驟就是劃分階段、確定狀態(tài)。這確定了是否能勝利運(yùn)用動(dòng)態(tài)

規(guī)劃方法。因此。確定一個(gè)可行的遞推思路是勝利的關(guān)鍵。

18

在這一過程中，要擅長(zhǎng)變通。

石子合并：N堆石子圍成一圈，每堆石子的量a[i]己知.每次可以將相鄰兩堆合并為一堆，將合并后

石子的總量記為這次合并的得分。N?1次合并后石子成為一堆。求這N?1次合并的得分之和可能的最大

值。

數(shù)據(jù)規(guī)模：N<100,a[i]<20000000

算法構(gòu)造：

分析數(shù)據(jù)規(guī)模一算法可承受的最大數(shù)據(jù)規(guī)模O(N^3),搜尋必定超時(shí)，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先

考慮動(dòng)態(tài)規(guī)劃。

遞推思路一計(jì)算將第i堆至第j堆完全合并所能獲得的最大得分。這是此題的關(guān)鍵?？紤]模擬每種合并

后的具體情形是行不通的。把問題變成這樣后就好解決了。

劃分階段一以合并的次數(shù)作為標(biāo)準(zhǔn)劃分階段。

確定狀態(tài)一第i堆至第j堆合并所能獲得的最大價(jià)值。

狀杰轉(zhuǎn)移方程---f(ij)=max{f(i,k)+f(k+lj)}rO<i<k<j^n

邊界狀態(tài)——f(ij)=a[i]

分析知時(shí)間困難度為。8人3),滿意要求。

遞推求出f(l,n)即可。動(dòng)態(tài)規(guī)劃特點(diǎn)是“思路難，實(shí)現(xiàn)易“，這里不再給出源代碼。

另外，NOIP2024出現(xiàn)了一道石子合并的衍生問題。

在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有

頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾

標(biāo)記確定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤(吸盤是Mars人汲取能量的一種器官)

的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤汲取的能量。假如前一顆能量珠的

頭標(biāo)記為m,尾標(biāo)記為r,后一顆能量珠的頭標(biāo)記為r,尾標(biāo)記為n,則聚合后釋放的能量為(Mars

單位)，新產(chǎn)生的珠子的頭標(biāo)記為m,尾標(biāo)記為n。

須要時(shí)，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。

明顯，不同的聚合依次得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合依次，使一串項(xiàng)鏈釋放出的總能量

最大。

建議讀者自己思索解決，以熟識(shí)動(dòng)態(tài)規(guī)劃的思維過程。在附件中給出解法的源代碼。

e.街道問題：狀態(tài)量維數(shù)的確定與無后效性

下面是動(dòng)態(tài)規(guī)劃的經(jīng)典問題之一：街道問題。

下圖表示一個(gè)街道?，F(xiàn)有類似這樣的N*N的街道，且每段路有一個(gè)權(quán)值?，F(xiàn)在要從左上角沿線走到右下

角，每次只能向右或向下走。求經(jīng)過路段權(quán)值和的最大值。

數(shù)據(jù)規(guī)模：N<1000

3256

IIIII

4|3728

2|3682

卜3+++T

6|8514

HH-5-+9-1-8-4

9|3281

分析數(shù)據(jù)規(guī)模一算法可承受的最大數(shù)據(jù)規(guī)模O（N人2）,搜尋必定超時(shí)，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先

考慮動(dòng)態(tài)規(guī)劃。

遞推思路一從左上角向右下角推，求出走到每一點(diǎn)所經(jīng)過權(quán)值和的最大值。

劃分階段一按斜向（/）劃分

19

剩下的讀者自己思索。時(shí)間困難度應(yīng)為0（n八2）。

上面問題中，若是改為從左上角沿線走到右下角再以不交叉的線路返回到動(dòng)身點(diǎn)，算法應(yīng)當(dāng)做怎樣的修

改？

原來的狀態(tài)已經(jīng)不能保證"不交叉”，在這種狀況下，我們用增加一維狀態(tài)量的方法，以探討是否交叉，

比較便利的思路一從左上角動(dòng)身兩條路，再向右下方遞推的過程中，兩條路的最末端始終不能是同一點(diǎn),

必需分布在這一階段的兩點(diǎn)上，直到最終在右下角匯合。

由于增加了一維狀態(tài)量，時(shí)間困難度變?yōu)?（n人3）。

f.0-1背包：奇妙地選取狀態(tài)量

有時(shí)，選定狀態(tài)時(shí)發(fā)覺不能運(yùn)用動(dòng)態(tài)規(guī)劃，或問題從表面上看讓人無所適從，我們不妨從另一個(gè)角度看

問題。

上一章我們介紹了部分背包問題，下面我們介紹更經(jīng)典的背包問題。

問題描述：有N件物品和一個(gè)最大載重為M的背包，每件物品都有相應(yīng)的重量和價(jià)值。現(xiàn)要求給出一個(gè)

存放方案，使背包中物品總價(jià)值最大。所涉及到的數(shù)字均為整數(shù)。

數(shù)據(jù)規(guī)模：1<N<1OO,l<M<10000o

這個(gè)問題與部分背包問題的區(qū)分在于，物品只能整件放入，不能只取一部分。這樣，背包很可能會(huì)有部

分載重量未利用。若用貪心法取單位重量?jī)r(jià)值高的，可能會(huì)使背包未利用的載重上升，得不到最優(yōu)方

案。

考慮到數(shù)據(jù)規(guī)模，選用動(dòng)態(tài)規(guī)劃法。

好像只有“每考慮一件物品為一階段”的劃分方法?？墒侨绾未_定狀態(tài)？很多人想不到這個(gè)方法：以一個(gè)

最大載重值為一個(gè)狀態(tài)。

完整遞推思路——