動態規劃算法分析

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

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

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

1 動態規劃算法的基本思想與步驟設計

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

2）動態規劃算法步驟設計 動態規劃算法適用于解最優化問題，一般可按以下步驟設計動態規劃算法：①找出最優解的特質，并描述其結構特征；②用遞歸的方式定義最優值；③以自下向上的方式計算出最優值；④根據計算最優值時得到的信息，構造最優解。

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

2 數字三角形問題的動態規劃算法求解

下面以數字三角形為例，說明動態規劃算法的具體實施。

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

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

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

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

3 動態規劃算法解題的一般思路

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

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

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

4 結 語

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

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

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

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

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