之前的兩個(gè)問題都是用動態(tài)規(guī)劃方法解決的，那么什么情況下需要使用動態(tài)規(guī)劃呢？適應(yīng)動態(tài)規(guī)劃方法求解的最優(yōu)化問題應(yīng)該具備的兩個(gè)要素：最優(yōu)子結(jié)構(gòu)和子問題重疊。
用動態(tài)規(guī)劃方法求解最優(yōu)化問題的第一步就是刻畫最優(yōu)解的結(jié)構(gòu)。如果一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解，就稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。使用動態(tài)規(guī)劃方法時(shí)，我們用子問題的最優(yōu)解來構(gòu)造原問題的最優(yōu)解，因此就要仔細(xì)考察最優(yōu)解中用到的所有子問題。 在發(fā)掘最優(yōu)子結(jié)構(gòu)性質(zhì)的過程中，遵循了如下的通用模式： 1. 證明問題最優(yōu)解的第一個(gè)組成部分是做出一個(gè)選擇，做出這次選擇會產(chǎn)生一個(gè)或多個(gè)待解的子問題。 2. 對于一個(gè)給定問題，在其可能的第一步選擇中，假定已經(jīng)知道哪種選擇才會得到最優(yōu)解，并不關(guān)心這種選擇具體是如何得到的，只是假定已經(jīng)知道了這種選擇。 3. 給定可獲得最優(yōu)解的選擇后，確定這次選擇會產(chǎn)生哪些子問題，以及如何最好地刻畫子問題空間。 4. 證明作為構(gòu)成原問題最優(yōu)解的組成部分，每個(gè)子問題的解就是它本身的最優(yōu)解，可利用反證法證明。 刻畫子問題空間的經(jīng)驗(yàn)是：保持子問題空間盡可能簡單，只在必要時(shí)才擴(kuò)展它。 對于不同問題領(lǐng)域，最優(yōu)子結(jié)構(gòu)體的不同體現(xiàn)在兩個(gè)方面： - 原問題的最優(yōu)解中涉及多少個(gè)子問題，以及 - 在確定最優(yōu)解使用那些子問題時(shí)，我們需要考察多少種選擇。 在動態(tài)規(guī)劃方法種，通常自底向上的使用最優(yōu)子結(jié)構(gòu)，也就是說，首先求得子問題的最優(yōu)解，然后求原問題的最優(yōu)解，在求解原問題過程中，需要在涉及的子問題中做出選擇，選擇得到原問題最優(yōu)解的子問題，原問題最優(yōu)解的代價(jià)通常就是子問題最優(yōu)解的代價(jià)加上由此次選擇直接產(chǎn)生的代價(jià)。 在嘗試使用動態(tài)規(guī)劃方法時(shí)要小心，要注意問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對于一個(gè)無權(quán)有向圖來說，無權(quán)最短路徑自然可以使用動態(tài)規(guī)劃方法進(jìn)行求解，但無權(quán)最長簡單路徑就不適用動態(tài)規(guī)劃方法了，原因是求解一個(gè)子問題時(shí)用到了某些資源，導(dǎo)致這些資源在求解其他子問題時(shí)不可用。
適合動態(tài)規(guī)劃方法求解的最優(yōu)化問題應(yīng)該具備的第二個(gè)性質(zhì)是子問題空間必須足夠“小”，即問題的遞歸算法會反復(fù)求解相同的子問題，而不是一直生成新的子問題，一般來講，不同子問題的總數(shù)是輸入規(guī)模的多項(xiàng)式函數(shù)為好，如果遞歸算法反復(fù)求解相同的子問題，就稱最優(yōu)化問題具有重疊子問題性質(zhì)，與之相對的，適合用分治方法求解的問題通常在遞歸的每一步都生成全新的子問題。 凡是一個(gè)問題的自然遞歸算法的遞歸調(diào)用樹中反復(fù)出現(xiàn)相同的子問題，而不同子問題的總數(shù)據(jù)很少時(shí)，動態(tài)規(guī)劃方法都能提高效率。 帶備忘的遞歸算法為每個(gè)子問題維護(hù)一個(gè)表項(xiàng)來保存它的解，每個(gè)表項(xiàng)的初值設(shè)為一個(gè)特殊值，表示尚未填入子問題的解，當(dāng)遞歸調(diào)用過程中第一次遇到子問題時(shí)，計(jì)算其解，并存入對應(yīng)表項(xiàng)，隨后每次遇到同一個(gè)子問題，只是簡單的查詢，返回其解。
最長公共子序列問題給定兩個(gè)序列X=（x1，x2，???，xm）和Y=（y1，y2，???，yn），求X和Y長度最長的公共子序列。
最優(yōu)子結(jié)構(gòu)：令X=（x1，x2，???，xm）和Y=（y1，y2，???，yn）為兩個(gè)序列，Z=（z1，z2，???，zk）為X和Y的任意最長公共子序列（LCS）。 - 如果xm=yn，則zk=xm=yn且Z（k-1）是X（m-1）和Y（n-1）的一個(gè)LCS。 - 如果xm≠yn，那么zk≠xm意味著Z是X（m-1）和Y的一個(gè)LCS。 - 如果xm≠yn，那么zk≠yn意味著Z是X和Y（n-1）的一個(gè)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]來構(gòu)造最優(yōu)解，b[i, j]指向的表項(xiàng)對應(yīng)計(jì)算c[i, j]時(shí)所選擇的子問題最優(yōu)解。偽代碼如下：
LCS_LENGTH(X, Y)m = X.lengthn = Y.lengthlet b[m + 1, n + 1] and c[m + 1, n + 1] be new arrayfor i = 1 to m c[i, 0] = 0for j = 1 to n c[0, j] = 0for i = 0 to m for j = 1 to n if x[i] == y[i] c[i, j] = c[i – 1, j – 1] + 1 b[i, j] = “↖” else if c[i – 1, j] >= c[i, j – 1] c[i, j] = c[i – 1, j] b[i, j] = “↑” else c[i, j] = c[i, j – 1] b[i, j] = “←”return c and b利用b[i, j]中的箭頭進(jìn)行追蹤打印，實(shí)現(xiàn)的偽代碼如下：
PRINT_LCS(b, X, i, j)if i == 0 or j == 0 returnif b[i, j] == “↖” PRINT_LCS(b, X, i - 1, j - 1) print x[i]else if b[i, j] == “↑” PRINT_LCS(b, X, i - 1, j)else PRINT_LCS(b, X, i, j - 1)新聞熱點(diǎn)
疑難解答
