在計算機算法設計方法中，動態規劃技術是比較基本，但又比較抽象，難于理解的一種。它建立在最優原則的基礎上，采用動態規劃方法，可以優雅而高效地解決許多用貪心技術或分治技術無法解決的問題。因此，動態規劃技術越來越成為解決許多重要的應用問題的關鍵技術。例如，用動態規劃解決0-1背包問題、圖像數據壓縮、矩陣連乘、有向圖最短路徑、無交叉子集、元件折疊以及最長公共子序列等應用問題。另外，在語音識別領域，應用動態規劃技術的動態時間伸縮算法DTW取得了很大成功，當詞匯表較小以及各個詞條不易于混淆時，DTW可以有效的解決孤立詞識別時說話速度不均勻的難題，從而自20世紀60年代末期掀起了語音識別研究的熱潮。
1 動態規劃技術的基本原理
1.1 算法思想
動態規劃與貪心策略類似，將一個問題的解決方案視為一系列決策的結果。不同的是，貪心算法每采用一次貪心選擇便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優決策自序列。使用動態規劃時，所求問題應具有以下兩種性質。
1.1.1 最優子結構性質
所求問題的最優子結構性質是采用動態規劃算法的條件之一，這種性質又被稱為最優化原理。動態規劃方法采用最優化原理來建立用于計算最優解的遞歸式。所謂最優化原理即不管前面的策略如何，此后的決策必須是基于當前狀態（由上一次決策產生）的最優決策。由于對于有些問題的某些遞歸式來說并不一定能保證最優原則，因此在求解問題時有必要對它進行驗證。若不能保持最優原則，則不可應用動態規劃方法。在得到最優解的遞歸式之后，需要執行回溯以構造最優解。當最優決策序列中包含最優決策子序列時，可建立動態規劃遞歸方程，它可以幫助我們高效地解決問題。
1.1.2 子結構重迭性質
人們總希望編寫一個簡單的遞歸程序來求解動態規劃遞歸方程。然而，如果不努力地去避免重復計算，遞歸程序的復雜性將非�？捎^。如果在遞歸程序設計中解決了重復計算問題，復雜性將大幅度下降。這種方法的思想是：由程序設置“備忘錄”，每計算出一個新的子結構的解時，都保存起來。當遇到一次遞歸時，判斷是否已經計算，如果已經計算，只需取出先前保存的結果既可。動態規劃遞歸方程也可用迭代方式來求解，這時很自然地避免了重復計算。盡管迭代程序與避免重復計算的遞歸程序有相同的復雜性，但迭代程序不需要附加的遞歸�？臻g，因此將比避免重復計算的遞歸程序更快。
2 動態規劃算法設計舉例
2.1 最短路徑
假設G中每條邊都有一個長度，每條有向路徑的長度等于該路徑中各邊的長度之和。對于每對頂點 ，在頂點i 與j 之間可能有多條路徑，各路徑的長度可能各不相同。我們定義從i 到j 的所有路徑中，具有最小長度的路徑為從i 到j 的最短路徑。將n 個頂點編號為1到n。令c (i, j, k)表示從i 到j 的最短路徑的長度，其中k 表示該路徑中的最大頂點。對于任意k＞0，如何確定c (i, j, k) 呢？中間頂點不超過k 的i 到j 的最短路徑有兩種可能：該路徑含或不含中間頂點k。若不含，則該路徑長度應為 ，否則長度為 。c(i, j, k) 可取兩者中的最小值。因此可得到如下遞歸式：
以上的遞歸式將一個k 級運算轉化為多個k-1 級運算，而多個k-1 級運算應比一個k 級運算簡單。如果用遞歸方法求解上式，則計算最終結果的復雜性將無法估量。經過計算可知，得到所有c (i, j, n) 的時間為 。當注意到某些c (i, j, k-1) 值可能被使用多次時，可以更高效地求解c (i, j, n)。利用避免重復計算c(i, j, k) 的方法，可將計算c 值的時間減少到 。這可通過遞歸方式或迭代方式來實現。迭代算法的C++偽代碼如下所示。
//尋找最短路徑的長度
//初始化ci，j，1）
for (int i=1; i <= n; i++)
for (int j=1; j <= n; j++)
c(i ,j, 0) = a (i, j); // a 是長度鄰接矩陣
//計算c( i ,j, k ) ( 0 < k < = n )
for(int k=1;k <= n;k++)
for(int i=1;i <= n;i++)
for(int j=1;j <= n;j++)
if(c(i, k, k-1)+c(k, j, k-1) < c(i, j, k - 1))
c(i, j, k) = c(i, k, k - 1) + c(k, j, k - 1);
else c(i, j, k) = c (i, j, k - 1) ;
2.2 0-1背包問題
在0-1的背包問題中，最優決策序列由最優決策子序列組成。假設 表示剩余容量為y，剩余物品為i，i + 1，…，n 時的最優解的值，即：
(2-1)
和
(2-2)
在該例中，可得出 ，所以 。接著利用返回值 計算 及 ，此時 ，又由 ，得 ，因此 ，此時 ，所以 ，即得 。
利用遞歸計算 的函數如下：
//計算f(i, y)
int F(int i, int y)
{
if (i == n) return (y < w[n]) ? 0 : p[n];
if (y < w[i]) return F(i+1,y);
return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);
}
通過分析可知，算法的時間復雜度為 �？梢�，直接遞歸的時間開銷是指數級的，必須加以改進。經過分析可以得到，遞歸程序中 經過了大量的重復計算。為了避免 的重復計算，可以利用前面討論過的“備忘錄”方法。具體做法為：定義一個用于保留已被計算出 值的映射表M，該表格的每一個元素是三元組 。在計算 之前，應檢查M中是否已包含一個三元組 ，其中*表示任意值。如果已包含，則從M中取出 的值，否則，對 進行計算并將計算所得的三元組 加入M。實際中M可以用Hash的形式存儲。
3 動態規劃技術在實際中的應用和最新研究進展
3.1 孤立詞語音識別系統的DTW算法
動態時間伸縮算法(Dynamic Time Warpping，簡稱DTW)，是日本學者板倉(Itakura)將動態規劃技術應用于解決孤立詞識別時的說話速度不均勻的難題，提出的把時間規整和距離測度計算結合起來的一種非線性歸整技術。設測試語音參數共有I楨矢量，而參考模板共有J楨矢量，且 ，則動態時間規整就是要尋找一個時間規整函數 ，它將測試矢量的時間軸i非線性的映射到模板的時間軸j上，并使該函數 滿足：
式中， 是第i楨測試矢量 和第j楨模板矢量 之間的距離測度，D則是處于最優時間規整情況下兩矢量的距離。
而實際使用中，DTW是采用動態規劃技術(DP)來加以具體實現的。通常，規整函數 被限制在一個平行四邊形內，它的一條邊的斜率為2，另一條邊的斜率為1/2。規整函數的起始點為(1,1)，終止點為(I,J)。 的斜率為0、1或2；否則就為1或2。我們的目的是尋找一個規整函數，在平行四邊形內由點(1,1)到點(I,J)具有最小代價函數�？偞鷥r函數的計算式為：
式中， 為匹配點 本身的代價， 是在 以前所有允許值中最小的一個。因此，總代價函數是該點本身的代價與帶到該點的最佳路徑的代價之和。當詞匯表較小以及各個詞條不易于混淆時，這個算法取得了很大的成功，從而自20世紀60年代末期掀起了語音識別研究的熱潮。直到現在，DTW算法仍然廣泛的應用于小詞匯量語音識別，說話人確認系統，嵌入式語音識別系統等各個領域。
3.2 最長公共子序列(LCS)及其衍生問題
LCS（最長公共子序列）問題可以簡單地描述如下：
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，B，A}，Y={B，D，C，A，B，A}，則序列{C，B，A}是X和Y的一個公共子序列，但它不是X和Y的一個最長公共子序列。序列{B，C，B，A}也是X和Y的一個公共子序列，它的長度為4，而且它是X和Y的一個最長公共子序列，因為X和Y沒有長度大于4的公共子序列。
最長公共子序列問題就是給定兩個序列X={x1,x2,…xm}和Y={y1,y2,…yn}，找出X和Y的一個最長公共子序列。對于這個問題比較容易想到的算法是窮舉，對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中記錄最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的每個子序列相應于下標集{1,2,...,m}的一個子集。因此，共有 個不同子序列，從而窮舉法搜索需要指數時間。
事實上，最長公共子序列問題具有最優子結構性質：
設序列X={x1,x2,…xm}和Y={y1,y2,…yn}的一個最長公共子序列為Z={z1,z2,…zk}，則
1. 若 ，則 ，且Zk-1是Xm-1和Yn-1的最長公共子序列。
2. 若 且 ，則Z是Xm-1和Y的最長公共子序列。
3. 若 且 ，則Z是X和Yn-1的最長公共子序列。
通過以上的結論，我們觀察到——兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列，這使我們有可能將算法的時間復雜度降低到多項式級別，因為這兩個序列的不同的前綴組合只有 個。并且，根據以上結論，我們可以得出計算Xi和Yj的最長公共子序列的長度 的公式:
當 或 時， 。
當 且 時， 。
當 且 時， 。
這樣一來，解決這個問題就比較容易了，通過建立遞推結構，可以得出下列算法：
//求序列X和Y的最長公共子序列
for (i=1;i<=m;i++)
　 c[i][0]=0;
for (i=1;i<=n;i++)
　 c[0][i]=0;
for (i=1;i<=m;i++)
{
　　for (j=1;j<=n; j++)
　　{
　　　if (x[i]==y[j])
　　　　c[i][j]=c[i-1][j-1]+1;
　　　else if (c[i-1][j]>=c[i][j-1])
　　　　c[i][j]=c[i-1][j];
　　　else
　　　　c[i][j]=c[i][j-1];
　　}
}
X和Y的最長公共子序列的長度就存于c[m][n]中，欲求出具體的子序列，則可通過數組的值用 的時間回推，具體的方法不再贅述。
4 結束語
動態規劃技術是基本算法設計技術中較難掌握但也是極其重要的一種方法，它的應用領域非常廣泛，除了本文提到的一些問題之外，動態規劃還用于解決字符串搜索問題、手寫字符識別問題、網絡的無交叉布線、電路元件折疊和旅行商問題等各種實際應用問題，因此，掌握動態規劃技術對提高計算機算法設計和分析水平及解決實際計算問題具有至關重要的作用和意義。
<