動態規劃法的教學引例
——數字三角形問題

張惠艷，陳芳

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

1 引言

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

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

2 問題描述

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

圖1 輸入樣式1

圖2 輸入樣式2

3 算法設計

3.1 深度優先搜索算法

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

深度優先搜索算法必然要遞歸實現，通過遞歸調用分析可知，若是10行的數字三角形，如圖3，每個子問題被遞歸調用的次數如圖4，10 行數字三角形中子問題調用最多的次數將達126次，這種算法設計方法大大降低了求解問題的效率，需要改進算法，提高效率。

圖3 10行的數字三角型

圖4 子問題被遞歸調用次數

3.2 記憶化搜索算法

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

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

圖5 記憶化搜索算法下子問題被遞歸調用次數

因為存儲每一次計算的結果，需要一個跟原數字三角形一樣大小的二維數組，犧牲了空間。既然已經犧牲了空間，能否進一步提高效率，消除遞歸？動態規劃法可消除遞歸，而且可追蹤出得到最大值的路徑，如圖1的最大值為30，路徑：7-＞3-＞8-＞7-＞5。

3.3 動態規劃法

數字三角形的遞歸求解存在重復的子問題，用表記錄子問題的解，以后可以直接使用。在求解最值的過程中，將三角形的每一行看成一個階段，因此有明顯的階段性，這是典型的坐標型問題，可采用動態規劃算法求解。對坐標型問題動態規劃法通常都有正推和倒推兩種實現方法。

正推：從a[0][0]出發，按照向下或右下方向一直走到最后一行，依次計算f[i][j]的值，遞推方程：f[i,j]=max(f[i-1,j-1],f[i-1,j])+a[i,j]，因為第一列從第二個元素開始只能用其正上方的元素求得，從第二行開始的對角線的元素只能由其斜上方的元素求得，因此遞推方程不適用邊界值，邊界值要單獨處理。問題的解需在二維數組f 的最后一行中求最大值，其C++實現代碼如下：

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

動態規劃法讓每個結點值只求解一次，時間復雜度仍為Ο(n2)，但消除了遞歸，大大改進了算法的效率。

4 路徑追蹤

動態規劃法求解問題不僅可以得到問題的解，還可以追蹤解的路徑。以順推法為例，在求解備忘錄f的過程中，增加標記數組m來記錄解是如何得到的，可以根據數組m來追蹤問題的解。其C++實現代碼如下：

5 結束語

數字三角形問題可采用不同的算法進行設計，不同的算法思想有不同的實現方法，不同的算法效率。在算法設計與分析課程中，建議在講解動態規劃法這一章節前加入這一引例，可以讓學生體會不同算法設計的思想，還可自然地過渡到動態規劃法求解問題的精髓——備忘錄和標記函數，激發學生對算法學習的興趣。最終為學生以高效的算法解決實際應用問題打下良好基礎[5]。