基本動態規劃問題的擴展
應用動態規劃可以有效的解決許多問題，其中有許多問題的數學模型，尤其對一些自從57年就開始研究的基本問題所應用的數學模型，都十分精巧。有關這些問題的解法，我們甚至可以視為標準——也就是最優的解法。不過隨著問題規模的擴大化，有些模型顯出了自身的不足和缺陷。這樣，我們就需要進一步優化和改造這些模型。
一. 程序上的優化：
程序上的優化主要依賴問題的特殊性。我們以f(XT)= opt{f(uT)}+ A(XT), uTÎ Pred_Set(XT)這樣的遞推方程式為例（其中A(XT)為一個關于XT的確定函數，Pred_Set(XT)表示XT的前趨集）。我們設狀態變量XT的維數為t，每個XT與前趨中有e維改變，則我們可以通過方程簡單的得到一個時間復雜度為O(nt+e)的算法。
當然，這樣的算法并不是最好的算法。為了簡化問題，得到一個更好的算法。我們設每個XT所對應的g(XT)=opt{f(uT)}，則f(XT)=g(XT)+A(XT)，問題就變為求g(XT)的值。下面分兩個方面討論這個問題：
1. Pred_Set(XT)為連續集：
在這樣的情況下，我們可以用g(XT)= opt{g(Pred(XT)), f(Pred(XT))}這樣一個方程式來求出g(XT)的值，并再用g(XT)的值求出f(XT)的值。這樣，雖然我們相當于對g(XT)和f(XT)分別作了一次動態規劃，但由于兩個規劃是同時進行的，時間復雜度卻降為了O(nt)。由于我們在實際使用中的前趨即通常都是連續的，故這個方法有很多應用。例如IOI’99的《小花店》一題就可以用該方法把表面上的時間復雜度O(FV2)降為O(FV)。
2. Pred_Set(XT)為與XT有關的集合：
這樣的問題比較復雜，我們以最長不下降子序列問題為例。規劃方程為：f(i)=max{f(j)}+1, d[i]≥ d[j]; i>j。通常認為，這個問題的最低可行時間復雜度為O(n2)。不過，這個問題只多了一個d[i]≥d[j]的限制，是不是也可以優化呢？我們注意到max{f(j)}的部分，它的時間復雜度為O(n)。但對于這樣的式子，我們通常都可以用一個優先隊列來使這個max運算的時間復雜度降至O(log n)。對于該問題，我們也可以用這樣的方法。在計算d[i]時，我們要先有一個平衡排序二叉樹（例如紅黑樹）對d[1]~d[i-1]進行排序。并且我們在樹的每一個節點新增一個MAX域記錄它的左子樹中的函數f的最大值。這樣，我們在計算f(i)時，只需用O(log n)時間找出不比d[i]大的最大數所對應的節點，并用O(1)的時間訪問它的MAX域就可以得出f(i)的值。并且，插入操作和更新MAX域的操作也都只用O(log n)的時間（我們不需要刪除操作），故總時間復雜度為O(n log n)。實際運行時這樣的程序也是十分快的，n=10000時用不到1秒就可以得出結果，而原來的程序需要30秒。
從以上的討論可以看出，再從程序設計上對問題優化時，要盡量減少問題的約束，盡可能的化為情況1。若不可以變為情況1，那么就要仔細考慮數據上的聯系，設計好的數據結構來解決問題。
二. 方程上的優化：
對于方程上的優化，其主要的方法就是通過某些數學結論對方程進行優化，避免不必要的運算。對于某一些特殊的問題，我們可以使用數學分析的方法對寫出的方程求最值，這樣甚至不用狀態之間的遞推計算就可以解決問題。不過用該方法解決的問題數量是在有限，并且這個方法也十分復雜。不過，卻的確有相當數量的比較一般的問題，在應用某些數學結論后，可以提高程序的效率。
一個比較典型的例子是最優排序二叉樹問題（CTSC96）。它的規劃方程如下：
我們可以從這個規劃方程上簡單的得到一個時間復雜度為O(n3)的算法。但是否會有更有效的算法呢？我們考慮一下w(i, j)的性質。它表示的是結點i到結點j的頻率之和。很明顯，若有[i, j]Í[i’, j’]，則有w[i, j]£ w[i’, j’]，這樣可知C[i, j]具有凸性[1]。為了表示方便，我們記Ck(i, j)=w(i, j)+C[i, k-1]+C[k, j]，并用Ki,j表示取到最優值C[i, j]時的Ck(i, j)的k值。我們令k=Ki,j-1，并取i< k’< k。由于k’< k£ j-1< j，故有：
C[k’, j-1]+ C[k, j]£ C[k’, j]+ C[k, j-1]
在等式兩側同時加上w(i, j-1)+ w(i, j)+C[i,. k-1]+ C[i, k’-1]，可得：
Ck’(i, j-1)+ Ck(i, j)£ Ck’(i, j)+ Ck(i, j-1)
由k的定義可知Ck(i, j-1)£ Ck’(i, j-1)，故Ck(i, j)£ Ck’(i, j)，所以k’¹ Ki,j，故Ki,j³ Ki,j-1。同理，我們可得Ki,j£ Ki+1,j，即Ki,j-1£Ki,j£Ki+1,j。這樣，我們就可以按對角線來劃分階段（就是按照j-i劃分階段）來求Ki,j。求Ki,j的時間復雜度為O(Ki+1,j-Ki,j-1+1)，故第d階段（即計算K1,1+d~Kn-d,n）共需時O(Kn-d+1,n-K1,d+n-d)£ O(n)。有共有n個階段，故總時間復雜度為O(n2)。
雖然這道題由于空間上的限制給這個算法的實際應用造成了困難，不過這種方法卻給我們以啟示。
我們在考慮IOI2000的POST問題。這一題的數學模型不是討論的重點，我們先不加討論，直接給出規劃方程 。從規劃方程直接得出的算法的時間復雜度為O(n3)。從這個規劃方程可以看出，它的每一階段都只與上一階段有關。故我們可以把方程變得簡單些，變為對如下的方程執行n次：
在遞推時，階段之間時沒有優化的余地的，故優化的重點就在于這個方程的優化上。我們用B[i, j]表示D[i]+w(i, j)，而原算法就是求出B并對每一列求最小值。
事實上，這一題的w有其特殊的性質：
對于a£ b£ c£ d，我們有w(a, c)+ w(b, d)£ w(a, d)+ w(b, c)。
這一性質對解題是應該有所幫助的。仿照上例，在兩側加上D[a]+ D[b]，可得B[a, c]+ B[b, d]£ B[a, d]+ B[b, c]。
也就是說，若B[a, c]³ B[b, c]，則有B[a, d]³ B[b, d]。于是我們在確定了B[a, c]與B[b, c]的大小關系之后，就可以決定是不是需要比較B[a, d]與B[b, d]的大小。
更進一步的，我們只要找出滿足B[a, h]³ B[b, h]的最小的h，就可以免去h之后對第a列的計算。而這樣的h，我們可以用二分查找法在O(log n)時間內找到（若w更特殊一些，例如說是確定的函數，我們甚至可以在O(1)的時間找到）。并且對于每一行來說，都只需要執行一次二分查找。在求出所有的h之后，只需用O(n)的時間對每列的第h行求值就可以了。這樣得出的總時間為O(n)+O(n log n)= O(n log n)。至于程序設計上的問題，雖然并不復雜，但不是15分鐘所可以解決的，也不是重點，略過不談。[2]不過由于該題目可以用滾動數組的技巧解決空間的問題，故在大數據量時該算法有優異的表現。
從上面的敘述可以看出，對于方程的優化主要取決于權函數w的性質。其中應用最多的就是w(a, c)+ w(b, d)£ w(a, d)+ w(b, c)這個不等式。實際上，這個式子被稱作函數的凸性判定不等式。在實際問題中，權函數通常都會滿足這個不等式或這是它的逆不等式。故這樣的優化應用是比較廣泛的。還有許多特殊的不等式，若可以在程序中應用，都可以提高程序的效率。
三. 從低維向高維的轉化：
在問題擴大規模時，有一種方式就是擴大問題的維數。這時，規劃時決策變量的維數也要增加。這樣，存儲的空間也要隨著成指數級增加，導致無法存儲下所有的狀態，這就是動態規劃的維數災難問題。如果我們還要在這種情況下使用動態規劃，那么就要使用極其復雜的數學分析方法。對于我們來說，使用這種方法顯然是不現實的。這時，我們就需要改造動態規劃的模型。通常我們都可以把這時的動態規劃模型變為網絡流模型。
對于模型的轉化方法，我們有一些一般的規律。若狀態轉移方程只與另一個狀態有關，我們可以肯定得到一個最小費用最大流的模型[3]。這個模型必然有其規律的地方，甚至用對偶算法在對網絡流的求解時也還要用到動態規劃的方法。不過這不是重點，我們關心的只是動態規劃問題如何轉化。例如說IOI’97《火星探測器》一題。這一題的一維模型是可以用動態規劃來解決的（這里的維數概念是指探測器的數目）。在維數增加時，我們就可以用該方法來用網絡流的方法解決問題。
除此之外，還有許多問題可以用該方法解決。例如最長區間覆蓋問題，在維數增加時也同樣可以用該方法解決。更進一步來說，甚至圖論的最短路問題也可以做同樣的轉化來求出特殊的最短路。不過一般來說轉化后流量最大為1，有許多特殊的性質也沒有得到應用，并且些復雜的動態規劃問題還無法轉化為網絡流問題（例如說最優二叉樹問題），故標準的網絡流算法顯然有些浪費，它的解決還需要進一步的研究。
參考文獻：
[EGG88] David Eppstein, Zvi Galil and Raffaele Giancarlo, Speeding up Dynamic Programming
[GP90] Zvi Galil and Kunsoo Park, Dynamic Programming with Convexity, Concavity, and Sparsity
[附錄]
[1] C[i, j]的凸性是指對于任意的a£ b£ c£ d，都有C[a, c]+ C[b, d]£ C[a, d]+ C[b, c]。它的證明如下：
我們設k=Kb,c，則有C[a, c]+ C[b, d]£ C[a, k-1]+ C[k, c]+ C[b, k-1]+ C[k, d]+ w(a, c)+ w(b, d)= C[a, k-1]+ C[k, d]+ w(a, d)+ C[b, k-1]+ C[k, c]+ w(b, c)= C[a, d]+ C[b, c]。得證。
[2] 有關這個問題的偽代碼如下：
begin
E[1]ßD[1];
Queue.Add(K:1, H:n);
for jß2 to n do
begin
if B(j-1, j)£ B(Queue.K[head], j) then
begin
E[j]ßB(j-1, j);
Queue.Empty;
Queue.Add(K:j-1, H:n+1);
end else
begin
E[j]ßB(Queue.K[head], j);
while B(j-1, Queue.H[tail-1])£ B(Queue.K[tail], Queue.H[tail-1]) do Queue.Delete(tail);
Queue.H[tail]ßh(Queue.K[tail], j-1);
if h_OK then Queue.Add(K:j-1, H:n+1);
end;
if Queue.H[head]=j+1 then Queue.SkipHead;
end;
end;
其中的隊列Queue可以稱作備選隊列，其中的隊列頭為第j行的最小值，并假設Queue.H[0]=j。其中的h(a, b)函數是用二分查找法查找B(a, h)³ B(b, h)的最小的h值，h_OK為查找成功與否的標志。在備選隊列Queue中的數據(K:ir, H:hr)的意義是：當行數在區間[hr-1, hr-1]的范圍內時，第ir列為最小值。
[3] 我們知道，動態規劃實際是求無向圖的最短路的一種方法，故我們可以把動態規劃中的每一個狀態看成一個點，并將狀態的轉移過程變為一個圖。在轉化為最小費用最大流時，我們把這一個點拆成兩個點，一個出點和一個入點，所有指向原來這個點的邊都與入點相連，且所有由原來這個點發出的邊現都以出點為起點。原來的邊的容量設為正無窮，邊權值一般不變。新增的入點與出點之間連一條邊，它的權值為點權值，容量為每一點可以經過的次數（一般為一）。并且建立一個超級源和一個超級匯，并與可能的入點和出點連邊。若有必要，超級源（或匯）也要拆成兩個點，并且兩個點之間的邊的容量為最大的可能容量，邊權值為0。這樣，用最小費用流的方法得出的解就是該問題多維情況下的接。