動(dòng)態(tài)規(guī)劃法的教學(xué)引例
——數(shù)字三角形問題

張惠艷，陳芳

(淮陰師范學(xué)院，江蘇淮安 223300)

1 引言

動(dòng)態(tài)規(guī)劃[1](Dynamic Programming 簡(jiǎn)稱DP)是解決“多階段決策問題”的一種高效算法。通過合理組合子問題的解從而解決整個(gè)問題解的一種算法。其中子問題并不是獨(dú)立的，這些子問題又包含有公共的子子問題。動(dòng)態(tài)規(guī)劃算法就是對(duì)每個(gè)子問題只求一次，并將其結(jié)果保存在一張表中(數(shù)組)，以后再用到時(shí)直接從表中拿過來使用，避免重復(fù)計(jì)算相同的子問題?！安蛔鰺o用功”的求解模式，大大提高了程序的效率。動(dòng)態(tài)規(guī)劃算法常用于解決統(tǒng)計(jì)類問題(統(tǒng)計(jì)方案總數(shù))和最優(yōu)值問題(最大值或最小值)，尤其普遍用于最優(yōu)化問題。動(dòng)態(tài)規(guī)劃算法能解決的問題主要分為線性型(如最長(zhǎng)公共子序列)，坐標(biāo)型(如多段圖問題，數(shù)字三角形)，區(qū)間型(如矩陣連乘)，背包型(如0-1 背包問題)，樹型(如選課問題)等。傳統(tǒng)講解方法都是直接用經(jīng)典例題背包問題[2]，不便于初學(xué)者理解重復(fù)子問題的產(chǎn)生、解決方法，以及動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)策略。

數(shù)字三角形問題曾是國(guó)際信息學(xué)(計(jì)算機(jī))奧林匹克競(jìng)賽的試題，這一問題可采用深度優(yōu)先搜索算法，記憶化搜索算法，以及動(dòng)態(tài)規(guī)劃法的方法來設(shè)計(jì)解決，可作為算法設(shè)計(jì)與分析課程中動(dòng)態(tài)規(guī)劃法這一章內(nèi)容的引例納入課程中講解。通過該例的三種不同算法設(shè)計(jì)的講解以及路徑的追蹤可以讓學(xué)生深刻體會(huì)深度優(yōu)先搜索算法遞歸解決該問題存在重復(fù)的子問題，大大降低了算法的效率；為了解決重復(fù)的子問題，提出了記憶化搜索算法，減少重復(fù)的子問題的求解，提高算法效率；進(jìn)一步分析發(fā)現(xiàn)數(shù)字三角形問題有明顯的階段性，可用表記錄子問題的解，以后可以直接使用，非常自然地過渡到動(dòng)態(tài)規(guī)劃的講解，提出動(dòng)態(tài)規(guī)劃法的備忘錄和路徑追蹤。所以此問題非常適合動(dòng)態(tài)規(guī)劃法教學(xué)的引例，便于學(xué)生理解該法的設(shè)計(jì)思想和適用問題，為動(dòng)態(tài)規(guī)劃法的教學(xué)做鋪墊。采用典型實(shí)例教學(xué)[3]，將復(fù)雜抽象算法理論與簡(jiǎn)單的典型實(shí)例有機(jī)結(jié)合，這樣使學(xué)生由被動(dòng)學(xué)習(xí)變?yōu)橹鲃?dòng)學(xué)習(xí)，培養(yǎng)學(xué)生對(duì)算法學(xué)習(xí)的興趣。同一問題的不同算法實(shí)現(xiàn)，對(duì)于提升學(xué)生的邏輯思維能力和編程解決實(shí)際問題的能力也有著非常重要的意義[4-5]，能為學(xué)生進(jìn)一步分析和解決計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域的復(fù)雜工程問題奠定良好基礎(chǔ)。

2 問題描述

有一個(gè)數(shù)字三角形，從最頂層出發(fā)，每一步只能向左下或右下方向走。編程求從最頂層到最底層的一條路所經(jīng)過位置上的數(shù)字之和的最大值。輸入樣例如圖1、圖2所示，為方便講解，用圖2向正下或右下方向走。輸出：一個(gè)正整數(shù)，路徑上數(shù)字之和的最大值。

圖1 輸入樣式1

圖2 輸入樣式2

3 算法設(shè)計(jì)

3.1 深度優(yōu)先搜索算法

深度優(yōu)先搜索(縮寫DFS)是對(duì)一個(gè)連通圖進(jìn)行遍歷的算法。它的思想是從一個(gè)頂點(diǎn)V0開始，沿著一條路一直走到底，這種盡量往深處走的概念即是深度優(yōu)先的概念。從數(shù)字三角形的第一個(gè)頂點(diǎn)向左下或右下方向一直走到最后一行的結(jié)點(diǎn)的過程就是深度優(yōu)先搜索，圖1、圖2的圖形可以理解為只是形狀不同，都可以采用二維數(shù)組a[Max][Max]存儲(chǔ)，Max 是數(shù)字三角形的行數(shù)，可在程序的開頭用const int 進(jìn)行定義。當(dāng)前結(jié)點(diǎn)的坐標(biāo)記為(i,j),左下方結(jié)點(diǎn)的坐標(biāo)可以標(biāo)記為(i+1,j)，右下方結(jié)點(diǎn)的坐標(biāo)可以標(biāo)記為(i+1,j+1)。數(shù)字三角形問題的深度優(yōu)先搜索算法的C++代碼可寫為：

深度優(yōu)先搜索算法必然要遞歸實(shí)現(xiàn)，通過遞歸調(diào)用分析可知，若是10行的數(shù)字三角形，如圖3，每個(gè)子問題被遞歸調(diào)用的次數(shù)如圖4，10 行數(shù)字三角形中子問題調(diào)用最多的次數(shù)將達(dá)126次，這種算法設(shè)計(jì)方法大大降低了求解問題的效率，需要改進(jìn)算法，提高效率。

圖3 10行的數(shù)字三角型

圖4 子問題被遞歸調(diào)用次數(shù)

3.2 記憶化搜索算法

記憶化搜索是在遞歸的過程中，將已經(jīng)計(jì)算出來的結(jié)果保存起來，之后再次用到時(shí)直接取出結(jié)果，避免重復(fù)運(yùn)算，可提高算法的效率。用二維數(shù)組a 記錄數(shù)字三角形，二維數(shù)組f 保存數(shù)字三角形中已經(jīng)計(jì)算出來的結(jié)點(diǎn)值，記憶化搜索算法的C++代碼為：

數(shù)組f的元素初始化-1，數(shù)組大小等同于數(shù)組a。記憶化搜索算法可使數(shù)字三角形每個(gè)子問題僅被計(jì)算一次，大大提高了算法的效率。若是10 行的數(shù)字三角形，如圖3，每個(gè)子問題被遞歸調(diào)用的次數(shù)如圖5，10行數(shù)字三角形中每個(gè)子問題最多被調(diào)用一次，所以算法的時(shí)間復(fù)雜度為Ο(n2)。

圖5 記憶化搜索算法下子問題被遞歸調(diào)用次數(shù)

因?yàn)榇鎯?chǔ)每一次計(jì)算的結(jié)果，需要一個(gè)跟原數(shù)字三角形一樣大小的二維數(shù)組，犧牲了空間。既然已經(jīng)犧牲了空間，能否進(jìn)一步提高效率，消除遞歸？動(dòng)態(tài)規(guī)劃法可消除遞歸，而且可追蹤出得到最大值的路徑，如圖1的最大值為30，路徑：7-＞3-＞8-＞7-＞5。

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

數(shù)字三角形的遞歸求解存在重復(fù)的子問題，用表記錄子問題的解，以后可以直接使用。在求解最值的過程中，將三角形的每一行看成一個(gè)階段，因此有明顯的階段性，這是典型的坐標(biāo)型問題，可采用動(dòng)態(tài)規(guī)劃算法求解。對(duì)坐標(biāo)型問題動(dòng)態(tài)規(guī)劃法通常都有正推和倒推兩種實(shí)現(xiàn)方法。

正推：從a[0][0]出發(fā)，按照向下或右下方向一直走到最后一行，依次計(jì)算f[i][j]的值，遞推方程：f[i,j]=max(f[i-1,j-1],f[i-1,j])+a[i,j]，因?yàn)榈谝涣袕牡诙€(gè)元素開始只能用其正上方的元素求得，從第二行開始的對(duì)角線的元素只能由其斜上方的元素求得，因此遞推方程不適用邊界值，邊界值要單獨(dú)處理。問題的解需在二維數(shù)組f 的最后一行中求最大值，其C++實(shí)現(xiàn)代碼如下：

倒推：從數(shù)組a 的最后一行出發(fā)，將最后一行先賦給數(shù)組f的對(duì)應(yīng)元素，按照向上或左上方向一直倒推到第一行，依次計(jì)算f[i][j]的值，遞推方程：f[i,j]=max(f[i+1,j],f[i+1,j+1])+a[i,j]，f[0][0]即是問題的解，其C++代碼如下：

動(dòng)態(tài)規(guī)劃法讓每個(gè)結(jié)點(diǎn)值只求解一次，時(shí)間復(fù)雜度仍為Ο(n2)，但消除了遞歸，大大改進(jìn)了算法的效率。

4 路徑追蹤

動(dòng)態(tài)規(guī)劃法求解問題不僅可以得到問題的解，還可以追蹤解的路徑。以順推法為例，在求解備忘錄f的過程中，增加標(biāo)記數(shù)組m來記錄解是如何得到的，可以根據(jù)數(shù)組m來追蹤問題的解。其C++實(shí)現(xiàn)代碼如下：

5 結(jié)束語

數(shù)字三角形問題可采用不同的算法進(jìn)行設(shè)計(jì)，不同的算法思想有不同的實(shí)現(xiàn)方法，不同的算法效率。在算法設(shè)計(jì)與分析課程中，建議在講解動(dòng)態(tài)規(guī)劃法這一章節(jié)前加入這一引例，可以讓學(xué)生體會(huì)不同算法設(shè)計(jì)的思想，還可自然地過渡到動(dòng)態(tài)規(guī)劃法求解問題的精髓——備忘錄和標(biāo)記函數(shù)，激發(fā)學(xué)生對(duì)算法學(xué)習(xí)的興趣。最終為學(xué)生以高效的算法解決實(shí)際應(yīng)用問題打下良好基礎(chǔ)[5]。