宛 楠 （皖南醫(yī)學院計算機教研室，安徽 蕪湖241000）

張 義 （安徽工程大學計算機與信息學院，安徽 蕪湖241000）

ACM國際大學生程序設(shè)計競賽 （簡稱ACM／ICPC）是由國際計算機界歷史悠久、頗具權(quán)威性的組織ACM學會 （Association for Computer Machinery）主辦，是世界上公認的規(guī)模最大、水平最高的國際大學生程序設(shè)計競賽，在信息技術(shù)界具有相當?shù)挠绊懥?，競賽的很多題目都是在實際的工程項目應(yīng)用中遇到的問題，能夠比較全面的考察學生對計算機以及其他學科知識的綜合運用能力，通過競賽可以系統(tǒng)的檢驗學生的計算機編程等方面的綜合水平，而這些正是IT從業(yè)者所急需的。在競賽中涉及到各種算法，其中動態(tài)規(guī)劃是較為常見的算法之一［1］。下面，筆者對動態(tài)規(guī)劃算法的進行了分析和研究?。

1 動態(tài)規(guī)劃算法的基本思想與步驟設(shè)計

1）動態(tài)規(guī)劃算法的基本思想 動態(tài)規(guī)劃算法基本思想是將所求解問題分解成若干個子問題，先求解子問題并保存已解決的子問題的答案，然后從這些子問題的解得到原問題的解。

2）動態(tài)規(guī)劃算法步驟設(shè)計 動態(tài)規(guī)劃算法適用于解最優(yōu)化問題，一般可按以下步驟設(shè)計動態(tài)規(guī)劃算法：①找出最優(yōu)解的特質(zhì)，并描述其結(jié)構(gòu)特征；②用遞歸的方式定義最優(yōu)值；③以自下向上的方式計算出最優(yōu)值；④根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。

步驟①～③是動態(tài)規(guī)劃算法的基本步驟。如果只需要求出最優(yōu)值，則步驟④可以省去。如果從最底層的子問題開始，自底向上地逐一推導出子問題的解，則編程的時候可不寫遞歸函數(shù)［2］。

2 數(shù)字三角形問題的動態(tài)規(guī)劃算法求解

下面以數(shù)字三角形為例，說明動態(tài)規(guī)劃算法的具體實施。

1）數(shù)字三角形問題描述 圖1給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，和最大的路徑稱為最佳路徑。問題是求出最佳路徑上的數(shù)字之和，路徑上的每一步只能從一個數(shù)走到下一層上和它最近的左邊的數(shù)或者右邊的數(shù)［3］。

2）具體實施過程 按照題目的要求，從頂點出發(fā)，假設(shè)先采用貪心法來求最佳路徑，每次選擇所能選的最大值作為下一步的路徑，則從頂點7出發(fā)選擇8，從8出發(fā)選擇1，從1出發(fā)選擇7，從7出發(fā)選擇5，所求最終路徑為7-8-1-7-5，如圖2所示，路徑和為28。然而，這個路徑并非題目所要求的最優(yōu)路徑，最優(yōu)路徑應(yīng)該為7-3-8-7-5，如圖3所示，路徑和為30。可見該問題采用自頂至下的貪心法是不能得到正確答案的。換言之，從頂點出發(fā)是無法直接判斷是選擇左下還是右下的數(shù)字。

轉(zhuǎn)換思路，從倒數(shù)第2層 （2、7、4、4）出發(fā)，則可以立刻做出判斷，即從2出發(fā)選擇5，從7出發(fā)選擇5，從4出發(fā)選擇6，4從出發(fā)選擇6，求和后更新該數(shù)字三角形，再從新的三角形的倒數(shù)第2層（8、1、0）出發(fā)，同樣可以立即做出判斷，即從8出發(fā)選擇12，從1出發(fā)選擇12，從0出發(fā)選擇10，求和后更新該數(shù)字三角形，依次類推直到最頂層，如圖4所示，此時該三角形只剩一個頂點，該頂點即為所求的最佳路徑和。這個過程就是動態(tài)規(guī)劃算法在求解該問題上的應(yīng)用。

3）算法實現(xiàn) 定義二維數(shù)組a來存放數(shù)字三角形，二維數(shù)組f來存放每次求和后產(chǎn)生的新數(shù)字三角形，則a［i，j］表示當前位置的值，f［i，j］表示在i、j這個位置能取得的最大值：

3 動態(tài)規(guī)劃算法解題的一般思路

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

具體到數(shù)字三角形的例子，子問題就是 “從位于（i，j）數(shù)字開始，到底邊路徑的最大和”。這個子問題和變量i，j相關(guān)，那么一個狀態(tài)就i，j的一組取值，即每個數(shù)字的位置就是一個狀態(tài)。該狀態(tài)所對應(yīng)的值，就是從該位置的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和，即源代碼中的f［i］［j］。

確定出什么是狀態(tài)以及在該狀態(tài)下的值后，就要明確不同的狀態(tài)之間怎樣遷移——即如何從一個或多個值已知的狀態(tài)，求出另一個狀態(tài)的值。狀態(tài)的遷移可以用遞推公式表示，該遞推公式又稱為 “狀態(tài)轉(zhuǎn)移方程”。如數(shù)字三角形中的狀態(tài)轉(zhuǎn)移方程為：

4 結(jié) 語

程序設(shè)計競賽是提高大學生綜合素質(zhì)的一個很好的平臺，在參賽的準備過程中會涉及到各種算法，其中動態(tài)規(guī)劃算法是最為常見的一種。筆者通過數(shù)字三角形詳細說明了動態(tài)規(guī)劃算法的解題過程，并給出了動態(tài)規(guī)劃算法解題一般思路，用動態(tài)規(guī)劃算法解題，應(yīng)該如何尋找子問題、定義狀態(tài)、狀態(tài)轉(zhuǎn)移方程是什么樣的，都需要具體問題具體分析。當然，筆者給出的例子屬簡單動態(tài)規(guī)劃，更為復雜的動態(tài)規(guī)劃算法如雙重動態(tài)規(guī)劃，還需進一步探討。

［1］王宏，吳文虎 ．清華實踐教學 “賽課結(jié)合”新思路 ［J］．計算機教育，2006（7）：12-14．

［2］劉汝佳 ．算法競賽入門 ［M］．北京：清華大學出版社，2009：158-159．

［3］李文新，郭煒，余華山 ．程序設(shè)計導引與在線實踐 ［M］．北京：清華大學出版社，2007：221-226．

［4］王曉東 ．算法設(shè)計與分析 ［M］．第2版 ．北京：清華大學出版社，2008：61-62．