關于動態(tài)規(guī)劃算法有效教學的思考

李建

摘 要：技術科目作為浙江省新高考科目以來，算法加試部分難度不斷提高。近幾年的考題對計數(shù)思想的考查，更標志著程序填空題的難度從代碼層面到思維深度的跨越。文章作者將結合思維程度的深入，逐步給出數(shù)個經典動態(tài)規(guī)劃問題的思考過程，并提出一種“加一維”的思考方法，切實有效提高學生解決動態(tài)規(guī)劃問題的能力。

關鍵詞：動態(tài)規(guī)劃;狀態(tài)定義;狀態(tài)轉移;加一維

中圖分類號：O221.3 文獻標識碼：A 收稿日期：2019-04-07 文章編號：1674-120X（2019）24-0117-02

很多教師錯誤地認為動態(tài)規(guī)劃問題就是背包問題，甚至有教師因為該問題太過抽象，“簡單粗暴”地讓學生死記背包模型代碼，顯然這種教學方法是非常不可取的。

下面筆者逐步給出數(shù)個經典動態(tài)規(guī)劃問題的解題步驟，建立概念之間的內在聯(lián)系，讓學生了解動態(tài)規(guī)劃算法的本質，并提出“加一維”，切實有效提高學生解決問題的能力。

一、動態(tài)規(guī)劃算法基本原理

在信息學競賽中，第一次考查動態(tài)規(guī)劃是在IOI1994（國際信息學競賽）中的“數(shù)塔問題”，雖然當時全世界信息學頂尖選手的此題得分率極低，但是現(xiàn)在已經作為DP算法的入門題出現(xiàn)。其模型比較直觀，有助于我們理解動態(tài)規(guī)劃算法中的相關概念和性質。很多教師在講授動態(tài)規(guī)劃時，先羅列相關生澀的概念，很多學生對此無法真正理解。下面我們從一個相對直觀的問題出發(fā)，一步一步引導學生主動思考，在解決問題的過程中，學生可以逐漸理解問題的本質。

問題一：數(shù)塔問題。有一些數(shù)字排成數(shù)塔的形狀，其中第一層有一個數(shù)字，第二層有兩個數(shù)字……第n層有n個數(shù)字?，F(xiàn)在要從第一層走到第n層，每次只能選擇左下方或者右下方的數(shù)字，問：“最后將路徑上所有數(shù)字相加后得到的和最大是多少？”

教師引導思考過程：

（1）從起點到第一行第一列的答案是固定的。

（2）在第一步驟基礎上，從起點到第二行的答案也是固定的。

（3）在第三行時，7有兩種選擇，顯然選擇累積更大的8才是最優(yōu)的。若將f[i][j]定義為從第一行第一列到第i行第j列的路徑上的數(shù)字和的最大值，則到數(shù)字7的遞推式為：f[3][2] = max（f[2][1] ， f[2][2]）+7。

（4）可得出一般遞推式為f[i][j]=max（f[i-1][j-1]，f[i-1][j]）+a[i][j]，我們只需要推到第n行，就可以得到ans=max（f[n][1…n]）。

解法提煉：

（1）狀態(tài)定義：f[i][j]定義從第一行第一列到第i行第j列的路徑上的數(shù)字和的最大值。

（2）所求：max（f[n][1…n]）。

（3）狀態(tài)轉移：f[i][j]=max（f[i-1][j-1]，f[i-1][j]）+a[i][j]。

正確性分析：

（1）前面推導的結果不會隨著后幾行得到的結果而改變——無后效性。

（2）局部最優(yōu)可以保證全局最優(yōu)——最優(yōu)子結構。

這兩個性質也是動態(tài)規(guī)劃算法解決問題的先決條件。

二、動態(tài)規(guī)劃的狀態(tài)定義

問題二：最長上升子序列問題。給定一個長度為n的數(shù)字序列，求最長的上升子序列長度。如3，1，2，6，4，5的最長上升子序列為1，2，4，5，故答案為4。

在問題一的基礎上，很容易想到如下解法。

（1）狀態(tài)定義：f[i]定義為到第i個數(shù)字為止，能獲得最長子序列長度。

（2）所求：f[n]。

（3）狀態(tài)轉移：顯然此時很難尋找到f[i]關于f[1…i-1]的遞推關系。

無法找到遞推關系是由于遞推時的大小關系需要第i個數(shù)與前面某個確定的數(shù)進行比較，而原有的狀態(tài)定義無法得知哪些數(shù)字被選中，故無法直接進行比較，帶著這個問題，容易想到新的解法。

（1）狀態(tài)定義：f[i]定義為到第i個數(shù)字為止，且第i個數(shù)必須為改子序列的最后一個數(shù)字時，所獲得的最長子序列的長度。

（2）所求：max（f[1…n]）。

（3）狀態(tài)轉移：f[i] = max（f[j]） + 1|1 <= j <= i - 1，a[j]

該算法的時間復雜度為0（n2），空間復雜度為0（n）。

問題三：最長公共子序列問題。給定兩個長度為n的數(shù)字序列，求最長的公共子序列長度。如第一個數(shù)字序列為1，6，2，5，4，7，第二個數(shù)字序列為1，2，5，5，2，7，則最長的公共子序列為1，2，5，7，其長度為4。

順著問題二的思路，可以得到如下解法。

（1）狀態(tài)定義：f[i][j]定義為當?shù)谝恍袛?shù)字取到第i個，第二行數(shù)字取到第j個時，所能得到的最長公共子序列長度，且第i個數(shù)字和第j個數(shù)字分別為所求子序列的最后一個數(shù)字（即這兩個數(shù)字必須取到）。

（2）所求：max（f[1…n][1…n]）。

（3）狀態(tài)轉移：

該解法狀態(tài)總數(shù)共有n2個，每個狀態(tài)需要枚舉i和j前面所有的p和q，求解單個狀態(tài)需要的枚舉量為（i-1）*（j-1），其時間復雜度是0（n2），總共有n2個狀態(tài)，故總的時間復雜度為0（n4），空間復雜度為0（n2）。該算法的瓶頸主要在于求解每個狀態(tài)都需要去枚舉前面所有的狀態(tài)，下面我們嘗試使用另外一種狀態(tài)定義來開拓學生的思路。

（1）狀態(tài)定義：f[i][j]定義為當?shù)谝恍袛?shù)字取到第i個，第二行數(shù)字取到第j個時，所能得到的最長子序列長度，且第i個數(shù)字和第j個數(shù)字不需要為所求子序列的最后一個數(shù)字（即這兩個數(shù)字取到與否都可以）。

（2）所求：f[n][n]。

（3）狀態(tài)轉移：

當a[i]與b[j]相等時，其會對目標值貢獻1，而a[i]與b[j]不相等時，顯然這兩個數(shù)字無法配對，故對f[i][j]而言，a[i]和b[j]中必有一個是多余的，故f[i][j]=max（f[i-1][j]，f[i][j-1]）。此時計算f[i][j]的時間復雜度為0（1），故總的時間復雜度為0（n2）。

經過前面三個問題的鋪墊，我們對解決動態(tài)規(guī)劃的問題的模式與思考方式有了一定了解，在此基礎上，我們再開始對更抽象的背包問題進行解答。

三、動態(tài)規(guī)劃算法在裝箱問題中的應用

問題四：裝箱問題。有一個箱子容量為V（正整數(shù)，0<=V<=20000），同時有n個物品（0

（1）狀態(tài)定義：f[i][j]定義為放到第i個物品為止，體積為j能否得到，1表示取到，0表示取不到。

（2）所求：V-max（j）|f[n][j]=1。

（3）狀態(tài)轉移：f[i][j]=f[i-1][j-a[i]]|f[i-1][j-a[i]]=1。

優(yōu)化一：觀察狀態(tài)轉移方程，f[i]僅與f[i-1]有關，故我們可以采用滾動數(shù)組來優(yōu)化空間，f[flag][j]=f[！flag][j-a[i]]|f[！flag][j-a[i]]=1，一輪計算完畢后，flag=！flag，此時空間復雜度從0（n*V）優(yōu)化到0（V）。

優(yōu)化二：只需要從大到小枚舉j就可保證同一個物品不會被計算多次，f[j]=f[j-a[i]]|f[j-a[i]]=1。

拓展思考：如果每個物品有無窮多個呢？

四、“加一維”思想在動態(tài)規(guī)劃問題中的應用

問題五：數(shù)塔問題加強版。在問題一的基礎上，增加一個條件：有且僅有一次機會可以將路徑中的一個數(shù)字獲得兩次，求最后路徑中路徑上數(shù)字的和的最大值。

顯然存在幾種明顯錯誤的貪心思想：

（1）在問題一基礎上，對路徑中最大的數(shù)字使用額外取一次的機會。

可構造如下反例：

1

1 ?8

14 8 8

經過問題一的處理，會發(fā)現(xiàn)路徑為1-8-8，再對路徑中最大值8額外取一次，最后結果為25，而顯然存在更優(yōu)的答案為1-1-14，其最后的結果為30。

（2）有了上述反例，又嘗試進行如下的貪心策略：將所有數(shù)字中最大的數(shù)字選定，再以這個數(shù)字為起點往上取到頂，往下取到最后一行，又可構造反例如：

1

1 ? 10

11 10 10

按照貪心策略，其路徑為1-1-11，結果為24，而存在答案為1-10-10，31。

正確做法就是本文要提出的“加一維”解法，引導思考過程：

（1）在不使用額外機會時，與問題一是完全一樣的。

（2）機會使用后，也與問題一是完全一樣的。

（3）每個數(shù)字都有使用該機會的可能性。

提出解法：

（1）狀態(tài)定義：f[i][j][k]定義為取到第i行第j列時，機會的狀態(tài)是k時能獲得的目標值最優(yōu)為多少，k為0表示機會已經使用，k為1表示機會尚未使用。

（2）所求：max（f[n][1..n][0]）。

（3）狀態(tài)轉移：

如果在第i行第j列時，機會依舊存在，則在此之前其機會也必須存在故遞推式為：f[i][j][1]=max（f[i-1][j-1][1]，f[i-1][j][1]）+a[i][j]。

如果機會已經被使用，則f[i][j][0]有兩種可能性：在此之前機會已經被使用max（f[i-1][j-1][0]，f[i-1][j][0]）+a[i][j]或者對a[i][j]使用取兩次的機會max（f[i-1][j-1][1]，f[i-1][j][1]）+2*a[i][j]，我們只需在這兩種可能性中取最大值便可。

我們把加入該機會是否被使用的狀態(tài)作為新的一維，枚舉其轉移時的所有可能性，巧妙地解決了該問題，且時間復雜度和空間復雜度依舊和原問題同階。這種技巧也在大量的動態(tài)規(guī)劃問題中適用，當我們無法很輕松地將“不可控的量”交代清楚時，可以將其狀態(tài)作為單獨的一維代入計算。

參考文獻：

[1]吳傳松.信息學奧賽中“動態(tài)規(guī)劃算法”的教學方法探究[J].中學理科園地，2008（3）：11-13.

[2]廖慧芬，邵小兵.動態(tài)規(guī)劃算法的原理及應用[J].中國科技信息，2005（21）：42.