一、動(dòng)態(tài)規(guī)劃的認(rèn)識(shí)
動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著《Dynamic Programming》，這是該領(lǐng)域的第一本著作。
1、已知問題規(guī)模為(i-1)的解，可以推導(dǎo)出問題規(guī)模為i的解，即：f(i) = F[f(i-1)]
這樣我們就可以一直向前推導(dǎo)，得到問題規(guī)模為0的狀態(tài)，這種規(guī)模的解一般是顯而易見的。這種方法也就是我們經(jīng)常使用的數(shù)學(xué)歸納法。
對(duì)于f(i), 我們只需要知道它的上一個(gè)狀態(tài)f(i-1)就可以完成的推理過程，而不需要更前序的狀態(tài)，我們將這個(gè)模型稱為馬爾科夫模型，對(duì)應(yīng)的推理過程叫做“貪心法”。
2、如果我們要求解問題規(guī)模為i的解，需要知道所有的前序狀態(tài)，即：f(i) = F[f(0), f(1), ..., f(i-1)], 這種求解方法也叫第二數(shù)學(xué)歸納法。
對(duì)于f(i)，我們需要知道這個(gè)狀態(tài)之前的所有前序狀態(tài)，才能完成的推理模型叫做高階馬爾科夫模型，對(duì)應(yīng)的推理過程叫做“動(dòng)態(tài)規(guī)劃法”。
二、基本思想
基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個(gè)子問題就是初始問題的解。
由于動(dòng)態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。
動(dòng)態(tài)規(guī)劃算法：它通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。
分治法：若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。
注：不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。
三、適用情況
能采用動(dòng)態(tài)規(guī)劃求解的問題的一般要具有3個(gè)性質(zhì)：
??? (1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。
??? (2) 無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
? ? (3) 有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)）
四、求解基本步驟
動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。
????初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
?? ? ? ? ? ? ? ? ? ? ?圖1 動(dòng)態(tài)規(guī)劃決策過程示意圖
(1)劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。
(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。
(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。
?? ?一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。
實(shí)際應(yīng)用中可以按以下幾個(gè)簡化的步驟進(jìn)行設(shè)計(jì)：
?? ?（1）分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。
?? ?（2）遞歸的定義最優(yōu)解。
?? ?（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值
?? ?（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解
五、算法基本框架
```
for(j=1; j<=m; j=j+1) // 第一個(gè)階段
? xn[j] = 初始值;
for(i=n-1; i>=1; i=i-1)// 其他n-1個(gè)階段
? for(j=1; j>=f(i); j=j+1)//f(i)與i有關(guān)的表達(dá)式
? ? xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子問題的最優(yōu)解求解整個(gè)問題的最優(yōu)解的方案
print(x1[j1]);
for(i=2; i<=n-1; i=i+1）
{?
? ? t = t-xi-1[ji];
? ? for(j=1; j>=f(i); j=j+1)
? ? ? ? if(t=xi[ji])
? ? ? ? ? ? break;
}
```
六、例解
leetcode: 516. 最長回文子序列
給定一個(gè)字符串s，找到其中最長的回文子序列?？梢约僭O(shè)s的最大長度為1000。
示例 1:
輸入:"bbbab"
輸出:4
一個(gè)可能的最長回文子序列為 "bbbb"。
示例 2:
輸入:"cbbd"
輸出:2
一個(gè)可能的最長回文子序列為 "bb"。??
分析：這個(gè)問題很顯然是要求一個(gè)最優(yōu)解的問題，考慮使用動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃問題求解的關(guān)鍵在于如何劃分狀態(tài)（即找出最優(yōu)子結(jié)構(gòu)，并且保證無后序性），也就是需要?jiǎng)澐智宄?dāng)前狀態(tài)和前一狀態(tài)，然后列出狀態(tài)之間的轉(zhuǎn)移方程和邊界條件。
對(duì)于這個(gè)問題，需要尋找字符串的最長回文子序列（子序列可以不連續(xù)），動(dòng)態(tài)規(guī)劃的思想是要將問題規(guī)模減小，用小規(guī)模的狀態(tài)解表示大規(guī)模的狀態(tài)解，直到邊界。那么分析回文序列的性質(zhì)，兩個(gè)不同長度字符串的回文長度有什么關(guān)系呢？
首先很顯然單個(gè)字符的回文長度為1，這個(gè)就可能是個(gè)邊界條件。基于這個(gè)邊界條件進(jìn)行規(guī)模擴(kuò)展，由于回文是對(duì)稱的，所以考慮向兩邊各加一個(gè)字符，那個(gè)這個(gè)更大規(guī)模的字符串的最長回文長度就可以表示為：?
```
if (a == b):
? ? f(i) = f(i-2) + 2
else:
? ? f(i) = max(前f(i-1)， 后f(i-1))
```
所以可以用f[i][j]表示字符串中子串i->j的最長回文長度，那么狀態(tài)轉(zhuǎn)移方程為：
如果 s 的第 i 個(gè)字符和第 j 個(gè)字符相同的話
```f[i][j] = f[i + 1][j - 1] + 2```
如果 s 的第 i 個(gè)字符和第 j 個(gè)字符不同的話
```f[i][j] = max(f[i + 1][j], f[i][j - 1])```
代碼如下：
```
class Solution {
? ? public int longestPalindromeSubseq(String s) {
? ? ? ? int n = s.length();
? ? ? ? int[][] f = new int[n][n];
? ? ? ? for (int i = n - 1; i >= 0; i--) {
? ? ? ? ? ? f[i][i] = 1;
? ? ? ? ? ? for (int j = i + 1; j < n; j++) {
? ? ? ? ? ? ? ? if (s.charAt(i) == s.charAt(j)) {
? ? ? ? ? ? ? ? ? ? f[i][j] = f[i + 1][j - 1] + 2;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return f[0][n - 1];
? ? }
}
```
記住，一般動(dòng)態(tài)規(guī)劃中會(huì)用一個(gè)二維數(shù)組記錄之前狀態(tài)的結(jié)果，便于后面直接使用。其實(shí)這樣空間消耗是比較大的o(n^2)，如果我們僅僅只需要知道前一個(gè)狀態(tài)的結(jié)果就可以，那么就不必將之前所有狀態(tài)結(jié)果保留，從而減少空間復(fù)雜度。
