動態規劃原理

    之前的兩個問題都是用動態規劃方法解決的，那么什么情況下需要使用動態規劃呢？適應動態規劃方法求解的最優化問題應該具備的兩個要素：最優子結構和子問題重疊。

最優子結構

    用動態規劃方法求解最優化問題的第一步就是刻畫最優解的結構。如果一個問題的最優解包含其子問題的最優解，就稱此問題具有最優子結構性質。使用動態規劃方法時，我們用子問題的最優解來構造原問題的最優解，因此就要仔細考察最優解中用到的所有子問題。     在發掘最優子結構性質的過程中，遵循了如下的通用模式： 1. 證明問題最優解的第一個組成部分是做出一個選擇，做出這次選擇會產生一個或多個待解的子問題。 2. 對于一個給定問題，在其可能的第一步選擇中，假定已經知道哪種選擇才會得到最優解，并不關心這種選擇具體是如何得到的，只是假定已經知道了這種選擇。 3. 給定可獲得最優解的選擇后，確定這次選擇會產生哪些子問題，以及如何最好地刻畫子問題空間。 4. 證明作為構成原問題最優解的組成部分，每個子問題的解就是它本身的最優解，可利用反證法證明。     刻畫子問題空間的經驗是：保持子問題空間盡可能簡單，只在必要時才擴展它。     對于不同問題領域，最優子結構體的不同體現在兩個方面： - 原問題的最優解中涉及多少個子問題，以及 - 在確定最優解使用那些子問題時，我們需要考察多少種選擇。     在動態規劃方法種，通常自底向上的使用最優子結構，也就是說，首先求得子問題的最優解，然后求原問題的最優解，在求解原問題過程中，需要在涉及的子問題中做出選擇，選擇得到原問題最優解的子問題，原問題最優解的代價通常就是子問題最優解的代價加上由此次選擇直接產生的代價。     在嘗試使用動態規劃方法時要小心，要注意問題是否具有最優子結構性質。對于一個無權有向圖來說，無權最短路徑自然可以使用動態規劃方法進行求解，但無權最長簡單路徑就不適用動態規劃方法了，原因是求解一個子問題時用到了某些資源，導致這些資源在求解其他子問題時不可用。

重疊子問題

    適合動態規劃方法求解的最優化問題應該具備的第二個性質是子問題空間必須足夠“小”，即問題的遞歸算法會反復求解相同的子問題，而不是一直生成新的子問題，一般來講，不同子問題的總數是輸入規模的多項式函數為好，如果遞歸算法反復求解相同的子問題，就稱最優化問題具有重疊子問題性質，與之相對的，適合用分治方法求解的問題通常在遞歸的每一步都生成全新的子問題。     凡是一個問題的自然遞歸算法的遞歸調用樹中反復出現相同的子問題，而不同子問題的總數據很少時，動態規劃方法都能提高效率。     帶備忘的遞歸算法為每個子問題維護一個表項來保存它的解，每個表項的初值設為一個特殊值，表示尚未填入子問題的解，當遞歸調用過程中第一次遇到子問題時，計算其解，并存入對應表項，隨后每次遇到同一個子問題，只是簡單的查詢，返回其解。

最長公共子序列

問題描述

    最長公共子序列問題給定兩個序列X=（x1，x2，???，xm）和Y=（y1，y2，???，yn），求X和Y長度最長的公共子序列。

最長公共子序列的特征

    最優子結構：令X=（x1，x2，???，xm）和Y=（y1，y2，???，yn）為兩個序列，Z=（z1，z2，???，zk）為X和Y的任意最長公共子序列（LCS）。 - 如果xm=yn，則zk=xm=yn且Z（k-1）是X（m-1）和Y（n-1）的一個LCS。 - 如果xm≠yn，那么zk≠xm意味著Z是X（m-1）和Y的一個LCS。 - 如果xm≠yn，那么zk≠yn意味著Z是X和Y（n-1）的一個LCS。

一個遞歸解

    定義c[i, j]表示Xi和Yj的LCS的長度，c[i, j]的取值可以由下面公式表示： 0, （i=0或j=0） c[i - 1, j - 1] + 1, （i,j > 0且xi=yj） max(c[i, j - 1], c[i – 1, j]), （i,j > 0且xi≠yi）

計算最優解的值

    通過輔助表b[i, j]來構造最優解，b[i, j]指向的表項對應計算c[i, j]時所選擇的子問題最優解。偽代碼如下：

構造最優解

    利用b[i, j]中的箭頭進行追蹤打印，實現的偽代碼如下：