动态规划算法的优化技巧
動態規劃是信息學競賽中一種常用的程序設計方法，本文著重討論了運用動態規劃思想解題時時間效率的優化。全文分為四個部分，首先討論了動態規劃時間效率優化的可行性和必要性，接著給出了動態規劃時間復雜度的決定因素，然后分別闡述了對各個決定因素的優化方法，最后總結全文。
[正文]
一、引言
動態規劃是一種重要的程序設計方法，在信息學競賽中具有廣泛的應用。
使用動態規劃方法解題，對于不少問題具有空間耗費大、時間效率高的特點，因此人們在研究動態規劃解題時更多的注意空間復雜度的優化，運用各種技巧將空間需求控制在軟硬件可以承受的范圍之內。但是，也有一部分問題在使用動態規劃思想解題時，時間效率并不能滿足要求，而且算法仍然存在優化的余地，這時，就需要考慮時間效率的優化。
本文討論的是在確定使用動態規劃思想解題的情況下，對原有的動態規劃解法的優化，以求降低算法的時間復雜度，使其能夠適用于更大的規模。
二、動態規劃時間復雜度的分析
使用動態規劃方法解題，對于不少問題之所以具有較高的時間效率，關鍵在于它減少了“冗余”。所謂“冗余”，就是指不必要的計算或重復計算部分，算法的冗余程度是決定算法效率的關鍵。動態規劃在將問題規模不斷縮小的同時，記錄已經求解過的子問題的解，充分利用求解結果，避免了反復求解同一子問題的現象，從而減少了冗余。
但是，動態規劃求解問題時，仍然存在冗余。它主要包括：求解無用的子問題，對結果無意義的引用等等。
下面給出動態規劃時間復雜度的決定因素：
時間復雜度=狀態總數*每個狀態轉移的狀態數*每次狀態轉移的時間[1]
下文就將分別討論對這三個因素的優化。這里需要指出的是：這三者之間不是相互獨立的，而是相互聯系，矛盾而統一的。有時，實現了某個因素的優化，另外兩個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，這就要求我們在優化時，堅持“全局觀”，實現三者的平衡。
三、動態規劃時間效率的優化
3.1 減少狀態總數
我們知道，動態規劃的求解過程實際上就是計算所有狀態值的過程，因此狀態的規模直接影響到算法的時間效率。所以，減少狀態總數是動態規劃優化的重要部分，本節將討論減少狀態總數的一些方法。
1、改進狀態表示
狀態的規模與狀態表示的方法密切相關，通過改進狀態表示減小狀態總數是應用較為普遍的一種方法。
例一、 Raucous Rockers 演唱組（USACO`96）
[問題描述]
現有n首由Raucous Rockers 演唱組錄制的珍貴的歌曲，計劃從中選擇一些歌曲來發行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標準進行選擇：
（1） 這組唱片中的歌曲必須按照它們創作的順序排序；
（2） 包含歌曲的總數盡可能多。
輸入n，m，t，和n首歌曲的長度，它們按照創作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數目。
（1≤n, m, t≤20）
[算法分析]
本題要求唱片中的歌曲必須按照它們創作順序排序，這就滿足了動態規劃的無后效性要求，啟發我們采用動態規劃進行解題。
分析可知，該問題具有最優子結構性質，即：設最優錄制方案中第i首歌錄制的位置是從第j張唱片的第k分鐘開始的，那么前j-1張唱片和第j張唱片的前k-1分鐘是前1..i-1首歌的最優錄制方案，也就是說，問題的最優解包含了子問題的最優解。
設n首歌曲按照寫作順序排序后的長度為long[1..n]，則動態規劃的狀態表示描述為：
g[i, j, k]，0≤i≤n，0≤j≤m，0≤k<t，表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數目，則問題的最優解為g[n,m,0]。由于歌曲i有發行和不發行兩種情況，而且還要分另加的k分鐘是否能錄制歌曲i。這樣我們可以得到如下的狀態轉移方程和邊界條件：
當k≥long，i≥1時：
g[i, j, k]=max{g[i-1,j,k-long]，g[i-1,j,k]}
當k<long，i≥1時：
g[i, j, k]=max{g[i-1,j-1,t-long]，g[i-1,j,k]}
規劃的邊界條件為：
當0≤k<t時：g[0,0,k]=0;
我們來分析上述算法的時間復雜度，上述算法的狀態總數為O(n*m*t)，每個狀態轉移的狀態數為O(1)，每次狀態轉移的時間為O(1)，所以總的時間復雜度為O(n*m*t)。由于n，m，t均不超過20，所以可以滿足要求。
[算法優化]
當數據規模較大時，上述算法就無法滿足要求，我們來考慮通過改進狀態表示提高算法的時間效率。
本題的最優目標是用給定長度的若干張唱片錄制盡可能多的歌曲，這實際上等價于在錄制給定數量的歌曲時盡可能少地使用唱片。所謂“盡可能少地使用唱片”，就是指使用的完整的唱片數盡可能少，或是在使用的完整的唱片數相同的情況下，另加的分鐘數盡可能少。分析可知，在這樣的最優目標之下，該問題同樣具有最優子結構性質，即：設D在前i首歌中選取j首歌錄制的最少唱片使用方案，那么若其中選取了第i首歌，則D-{i}是在前i-1首歌中選取j-1首歌錄制的最少唱片使用方案，否則D前i-1首歌中選取j首歌錄制的最少唱片使用方案，同樣，問題的最優解包含了子問題的最優解。
改進的狀態表示描述為：
g[i, j]=(a, b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。由于第i首歌分為發行和不發行兩種情況，這樣我們可以得到如下的狀態轉移方程和邊界條件：
g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long}
其中(a, b)+long=(a’, b’)的計算方法為：
當long≤t-b時： a’=a;? ???b’=b+long;
當long>t-b時： a’=a+1;? ?b’=long;
規劃的邊界條件：
g[i,0]=(0,0)??0≤i≤n
這樣題目所求的最大值是：ans=max{k| g[n, k]≤(m-1,t)}
改進后的算法，狀態總數為O(n2)，每個狀態轉移的狀態數為O(1)，每次狀態轉移的時間為O(1)，所以總的時間復雜度為O(n2)。值得注意的是，算法的空間復雜度也由改進前的O(m*n*t)降至優化后的O(n2)。
（程序及優化前后的運行結果比較見附件）
通過對本題的優化，我們認識到：應用不同的狀態表示方法設計出的動態規劃算法的性能也迥然不同。改進狀態表示可以減少狀態總數，進而降低算法的時間復雜度。在降低算法的時間復雜度的同時，也降低了算法的空間復雜度。因此，減少狀態總數在動態規劃的優化中占有重要的地位。
2、選擇適當的規劃方向
? ? 動態規劃方法的實現中，規劃方向的選擇主要有兩種：順推和逆推。在有些情況下，選取不同的規劃方向，程序的時間效率也有所不同。一般地，若初始狀態確定，目標狀態不確定，則應考慮采用順推，反之，若目標狀態確定，而初始狀態不確定，就應該考慮采用逆推。那么，若是初始狀態和目標狀態都已確定，一般情況下順推和逆推都可以選用，但是，能否考慮選用雙向規劃呢？
雙向搜索的方法已為大家所熟知，它的主要思想是：在狀態空間十分龐大，而初始狀態和目標狀態又都已確定的情況下，由于擴展的狀態量是指數級增長的，于是為了減少狀態的規模，分別從初始狀態和目標狀態兩個方向進行擴展，并在兩者的交匯處得到問題的解。
上述優化思想能否也應用到動態規劃之中呢？來看下面這個例子。
例二、 Divide (Merc`2000)
[問題描述]
有價值分別為1..6的大理石各a[1..6]塊，現要將它們分成兩部分，使得兩部分價值和相等，問是否可以實現。其中大理石的總數不超過20000。(英文試題詳見附件)
[算法分析]
令S=∑(i*a)，若S為奇數，則不可能實現，否則令Mid=S/2，則問題轉化為能否從給定的大理石中選取部分大理石，使其價值和為Mid。
這實際上是母函數問題，用動態規劃求解也是等價的。
m[i, j]，0≤i≤6，0≤j≤Mid，表示能否從價值為1..i的大理石中選出部分大理石，使其價值和為j，若能，則用true表示，否則用false表示。則狀態轉移方程為：
m[i, j]=m[i, j]??OR??m[i-1,j-i*k]? ?? ?? ?(0≤k≤a)
規劃的邊界條件為：m[i,0]=true； 0≤i≤6
若m[i, Mid]=true，0≤i≤6，則可以實現題目要求，否則不可能實現。
我們來分析上述算法的時間性能，上述算法中每個狀態可能轉移的狀態數為a，每次狀態轉移的時間為O(1)，而狀態總數是所有值為true的狀態的總數，實際上就是母函數中項的數目。
[算法優化]
實踐發現：本題在i較小時，由于可選取的大理石的價值品種單一，數量也較少，因此值為true的狀態也較少，但隨著i的增大，大理石價值品種和數量的增多，值為true的狀態也急劇增多，使得規劃過程的速度減慢，影響了算法的時間效率。
另一方面，我們注意到我們關心的僅是能否得到價值和為Mid的值為true的狀態，那么，我們能否從兩個方向分別進行規劃，分別求出從價值為1..3的大理石中選出部分大理石所能獲得的所有價值和，和從價值為4..6的大理石中選出部分大理石所能獲得的所有價值和。最后通過判斷兩者中是否存在和為Mid的價值和，由此，可以得出問題的解。
狀態轉移方程改進為：
當i≤3時：
m[i, j]=m[i, j]??OR??m[i-1,j-i*k]? ?? ?? ?(1≤k≤a)
當i>3時：
m[i, j]=m[i, j]??OR??m[i+1,j-i*k]? ?? ???(1≤k≤a)
規劃的邊界條件為：m[i,0]=true； 0≤i≤7
這樣，若存在k，使得m[3,k]=true, m[4,Mid-k]=true，則可以實現題目要求，否則無法實現。
（程序及優化前后的運行結果比較見附件）
從上圖可以看出雙向動態規劃與單向動態規劃在計算的狀態總數上的差異。
回顧本題的優化過程可以發現：本題的實際背景與雙向搜索的背景十分相似，同樣有龐大的狀態空間，有確定的初始狀態和目標狀態，狀態量都迅速增長，而且可以實現交匯的判斷。因此，由本題的優化過程，我們認識到，雙向擴展以減少狀態量的方法不僅適用于搜索，同樣適用于動態規劃。這種在不同解題方法中，尋找共通的屬性，從而借用相同的優化思想，可以使我們不斷創造出新的方法。
3.2??減少每個狀態轉移的狀態數
在使用動態規劃方法解題時，對當前狀態的計算都是進行一些決策并引用相應的已經計算過的狀態，這個過程稱為“狀態轉移”。因此，每個狀態可能做出的決策數，也就是每個狀態可能轉移的狀態數是決定動態規劃算法時間復雜度的一個重要因素。本節將討論減少每個狀態可能轉移的狀態數的一些方法。
1、四邊形不等式和決策的單調性
例三、石子合并問題(NOI`95)
[問題描述]
??在一個操場上擺放著一排n（n≤20）堆石子。現要將石子有次序地合并成一堆。規定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分。
試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應的合并方案。
[算法分析]
這道題是動態規劃的經典應用。由于最大得分和最小得分是類似的，所以這里僅對最小得分進行討論。設n堆石子依次編號為1，2，…..，n。各堆石子數為d[1..n]，則動態規劃的狀態表示為：
m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最小得分，則狀態轉移方程和邊界條件為：
m[i,j]=0? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???i=j
? ???i＜j
同時令s[i,j]=k，表示合并的斷開位置，便于在計算出最優值后構造出最優解。
上式中 的計算，可在預處理時計算 ，i=1..n；t[0]=0, 則：
上述算法的狀態總數為O(n2)，每個狀態轉移的狀態數為O(n)，每次狀態轉移的時間為O(1)，所以總的時間復雜度為O(n3)。
[算法優化]
當函數w[i,j]滿足??時，稱w滿足四邊形不等式[2]。
當函數w[i,j]滿足w[i’,j]≤w[i,j’]??時稱w關于區間包含關系單調。
在石子歸并問題中，令w[i,j]=??，則w[i,j]滿足四邊形不等式，同時由d≥0,t≥0可知w[i,j]滿足單調性。
m[i,j]=0? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???i=j
? ?i<j? ?? ?? ?…………①
對于滿足四邊形不等式的單調函數w，可推知由遞推式①定義的函數m[i,j]也滿足四邊形不等式，即??。這一性質可用數學歸納法證明如下：
我們對四邊形不等式中“長度”l=j’-i進行歸納：
當i=i’或j=j’時，不等式顯然成立。由此可知，當l≤1時，函數m滿足四邊形不等式。
下面分兩種情形進行歸納證明：
情形1：i<i’=j<j’
在這種情形下，四邊形不等式簡化為如下的反三角不等式：m[i,j]+m[j,j’] ≤m[i,j’]，設k=max{p | m[i,j’]=m[i,p-1]+m[p,j’]+w[i,j’] }，再分兩種情形k≤j或k>j。下面只討論k≤j，k>j的情況是類似的。
情形1.1：k≤j，此時：
情形2：i<i’<j<j’
設 y=max{p | m[i’,j]=m[i’,p-1]+m[p,j]+w[i’,j] }
? ?z=max{p | m[i,j’]=m[i,p-1]+m[p,j’]+w[i,j’] }
仍需再分兩種情形討論，即z≤y或z>y。下面只討論z≤y，z>y的情況是類似的。
由i<z≤y≤j有：
綜上所述，m[i,j]滿足四邊形不等式。
令s[i,j]=max{k | m[i,j]=m[i,k-1]+m[k,j]+w[i,j] }
由函數m[i,j]滿足四邊形不等式可以推出函數s[i,j]的單調性，即
s[i,j]≤s[i,j+1]≤s[i+1,j+1],? ???i≤j
當i=j時，單調性顯然成立。因此下面只討論i<j的情形。由于對稱性，只要證明s[i,j]≤s[i,j+1]。
令mk[i,j]=m[i,k-1]+m[k,j]+w[i,j]。要證明s[i,j]≤s[i,j+1]，只要證明對于所有i<k≤k’≤j且mk’[i,j]≤mk[i,j]，有：mk’[i,j+1]≤mk[i,j+1]。
事實上，我們可以證明一個更強的不等式
mk[i,j]-mk’[i,j]≤mk[i,j+1]-mk’[i,j+1]
也就是：? ?? ?? ???mk[i,j]+mk’[i,j+1]≤mk[i,j+1]+mk’[i,j]
利用遞推定義式將其展開整理可得：m[k,j]+m[k’,j+1]≤m[k’,j]+m[k,j+1]，這正是k≤k’≤j<j+1時的四邊形不等式。
綜上所述，當w滿足四邊形不等式時，函數s[i,j]具有單調性。
于是，我們利用s[i,j]的單調性，得到優化的狀態轉移方程為：
m[i,j]=0? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? i=j
? ?? ?i<j
用類似的方法可以證明，對于最大得分問題，也可采用同樣的優化方法。
改進后的狀態轉移方程所需的計算時間為
（程序及優化前后的運行結果比較見附件）
上述方法利用四邊形不等式推出最優決策的單調性，從而減少每個狀態轉移的狀態數，降低算法的時間復雜度。
上述方法是具有普遍性的。對于狀態轉移方程與①式類似，且w[i,j]滿足四邊形不等式的動態規劃問題，都可以采用相同的優化方法，如最優二叉排序樹（NOI`96）等。下面再舉一例。
例四、郵局(IOI`2000)
[問題描述]
按照遞增順序給出一條直線上坐標互不相同的n個村莊，要求從中選擇p個村莊建立郵局，每個村莊使用離它最近的那個郵局，使得所有村莊到各自所使用的郵局的距離總和最小。
試編程計算最小距離和，以及郵局建立方案。
[算法分析]
本題也是一道動態規劃問題，詳細分析請看文本附件（郵局解題報告）。將n個村莊按坐標遞增依次編號為1，2，……，n，各個郵局的坐標為d[1..n]，狀態表示描述為：m[i,j]表示在前j個村莊建立i個郵局的最小距離和。所以，m[p,n]即為問題的解，且狀態轉移方程和邊界條件為：
m[1,j]=w[1,j]
? ?? ?? ? i≤j
其中w[i,j]表示在d[i..j]之間建立一個郵局的最小距離和，可以證明，當僅建立一個郵局時，最優解出現在中位數，即設建立郵局的村莊為k，則 ，于是，我們有：
? ?，? ?
同時，令s[i,j]=k，記錄使用前i-1個郵局的村莊數，便于在算出最小距離和之后構造最優建立方案。
上述算法中w[i,j]可通過O(n)時間的預處理，在O(1)的時間內算出，所以，該算法的狀態總數為O(n*p)，每個狀態轉移的狀態數為O(n)，每次狀態轉移的時間為O(1)，該算法總的時間復雜度為O(p*n2)。
[算法優化]
本題的狀態轉移方程與①式十分相似，因此我們猜想其決策是否也滿足單調性，即
s[i-1,j]≤s[i,j]≤s[i,j+1]
首先，我們來證明函數w滿足四邊形不等式，即：
? ?
設 ， ，下面分為兩種情形，z≤y或z>y，下面僅討論z≤y，z>y的情況是類似的。
由i≤z≤y≤j有：
接著，我們用數學歸納法證明函數m也滿足四邊形不等式。對四邊形不等式中“長度”l=j’-i進行歸納：
當i=i’或j=j’時，不等式顯然成立。由此可知，當l≤1時，函數m滿足四邊形不等式。
下面分兩種情形進行歸納證明：
情形1：i<i’=j<j’，即m[i,j]+m[j,j’] ≤m[i,j’]，
設k=max{p | m[i,j’]=m[i,p-1]+m[p,j’]+w[i,j’] }，再分兩種情形k≤j或k>j。下面只討論k≤j，k>j的情況是類似的。
情形2：i<i’<j<j’
設??y=max{p | m[i’,j]=m[i’-1,p]+w[p+1,j] }
z=max{p | m[i,j’]=m[i-1,p]+w[p+1,j’] }
仍需再分兩種情形討論，即z≤y或z>y。
情形2.1，當z≤y<j<j’時：
情形2.2，當i-1<i’-1≤y<z<j’時：
最后，我們證明決策s[i,j]滿足單調性。
為討論方便，令mk[i,j]=m[i-1,k]+w[k+1,j]；
我們先來證明s[i-1,j]≤s[i,j]，只要證明對于所有i≤k<k’<j且mk’[i-1,j]≤mk[i-1,j]，有：mk’[i,j]≤mk[i,j]。
類似地，我們可以證明一個更強的不等式
mk[i-1,j]-mk’[i-1,j]≤mk[i,j]-mk’[i,j]
也就是：? ?? ?? ???mk[i-1,j]+mk’[i,j]≤mk[i,j]+mk’[i-1,j]
利用遞推定義式展開整理的：m[i-2,k]+m[i-1,k’]≤m[i-1,k]+m[i-2,k’]，這就是i-2<i-1<k<k’時m的四邊形不等式。
我們再來證明s[i,j]≤s[i,j+1]，與上文類似，設k<k’<j，則我們只需證明一個更強的不等式：? ?? ?? ?? ? mk[i,j]-mk’[i,j]≤mk[i,j+1]-mk’[i,j+1]
也就是：? ?? ?? ???mk[i,j]+mk’[i,j+1]≤mk[i,j+1]+mk’[i,j]
利用遞推定義式展開整理的：w[k+1,j]+w[k’+1,j+1]≤w[k+1,j+1]+w[k’+1,j]，這就是k+1<k’+1<j<j+1時w的四邊形不等式。
綜上所述，該問題的決策s[i,j]具有單調性，于是優化后的狀態轉移方程為：
m[1,j]=w[1,j]
? ?? ?? ? i≤j
s[i,j]=k
同上文所述，優化后的算法時間復雜度為O(n*p)。
（程序及優化前后的運行結果比較見附件）
? ?四邊形不等式優化的實質是對結果的充分利用。它通過分析狀態值之間的特殊關系，推出了最優決策的單調性，從而在計算當前狀態時，利用已經計算過的狀態所做出的最優決策，減少了當前的決策量。這就啟發我們，在應用動態規劃解題時，不僅可以實現狀態值的充分利用，也可以實現最優決策的充分利用。這實際上是從另一個角度實現了“減少冗余”。
2、決策量的優化
通過分析問題最優解所具備的性質，從而縮小有可能產生最優解的決策集合，也是減少每個狀態可能轉移的狀態數的一種方法。
大家所熟悉的NOI`96中的添加號問題，正是從“所得的和最小”這一原則出發，僅在等分點的附近添加號，從而大大減少了每個狀態轉移的狀態數，降低了算法的時間復雜度。讓我們在再來看一例。
例五、石子歸并的最大得分問題
[問題描述]
見例三，本例只考慮最大得分問題。
[算法分析]
設n堆石子依次編號為1，2，…..，n。各堆石子數為d[1..n]，則動態規劃的狀態表示為：
m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最大得分，則狀態轉移方程和邊界條件為：
m[i,j]=0? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???i=j
? ???i＜j
同時令s[i,j]=k，表示合并的斷開位置，便于在計算出最優值后構造出最優解。
? ? 該算法的時間復雜度為O(n3)。
[算法優化]
仔細分析問題，可以發現：s[i,j]要么等于i+1，要么等于j，即：
證明可以采用反證法，設使m[i,j]達到最大值的斷開位置為p，且i+1<p<j， ， ，下面分為2種情形討論。
情形1、y≥z
由p<j，可設s[p,j]=k，則相應的合并方式可以表示為：
(??(a…a[p-1])??( (a[p]...a[k-1]) (a[k]..a[j]) screen.width/2)this.width=screen.width/2" vspace=2 border=0>??screen.width/2)this.width=screen.width/2" vspace=2 border=0>
相應的得分為： …………①
下面考慮另一種合并方案s’[i,j]=k，s’[i,k]=p，表示為：
( ( (a…a[p-1]) (a[p]...a[k-1]) screen.width/2)this.width=screen.width/2" vspace=2 border=0>??(a[k]..a[j])? ?screen.width/2)this.width=screen.width/2" vspace=2 border=0>
相應的得分為： …………②
由y≥z可得，T<T’，這與使m[i,j]達到最大值的斷開位置為p的假設矛盾。
情形2、y<z??與情形1類似。
于是，狀態轉移方程優化為：
m[i,j]=0? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???i=j
? ???i＜j
優化后每個狀態轉移的狀態數減少為O(1)，算法總的時間復雜度也降為O(n2)。
（程序及優化前后的運行結果比較見附件）
本題的優化過程是通過對問題最優解性質的分析，找出最優決策必須滿足的必要條件，這與搜索中的最優性剪枝的思想十分類似，由此我們再次看到了相同的優化思想應用于不同的算法設計方法。同時，我們也認識到：動態規劃的優化必須建立在全面細致分析問題的基礎上，只有深入分析問題的屬性，挖掘問題的實質，才能實現算法的優化。
總結
以上是生活随笔為你收集整理的动态规划算法的优化技巧的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 九度OJ 重复子串
- 下一篇： 回溯法+奇偶剪枝——Hdu 1010 T