在上一篇中 動態(tài)規(guī)劃算法（一)
由幾個經(jīng)典問題：斐波那契數(shù)列，登臺階問題以及最大連續(xù)子數(shù)組問題，對動態(tài)規(guī)劃有了一個基本的認(rèn)知。
動態(tài)規(guī)劃大約由數(shù)學(xué)家理查德·貝爾曼在40年代發(fā)明，在數(shù)學(xué)，管理科學(xué)，計算機(jī)科學(xué)，經(jīng)濟(jì)學(xué)，和生物信息學(xué)都有運(yùn)用。一般用于解決具有最優(yōu)子問題結(jié)果，并且子問題具有重疊特性的問題。
動態(tài)規(guī)劃一般的設(shè)計方法如下：
刻畫出一個最優(yōu)解的結(jié)構(gòu)特征。對于斐波那契數(shù)列遞推式，它的結(jié)構(gòu)特征即蘊(yùn)含在它的遞推式中；對于最大連續(xù)子數(shù)組問題，它的結(jié)構(gòu)特征則是需要適當(dāng)?shù)臉?gòu)造，我們構(gòu)造了一組特征數(shù)：以每個成員為右界的最大連續(xù)子數(shù)組的和。
遞歸定義最優(yōu)解的值 ，幾乎大多數(shù)動態(tài)規(guī)劃問題都能轉(zhuǎn)化為數(shù)學(xué)公式的形式，左邊是待求解的F(n), 右邊可能是由若干子問題表達(dá)的式子。有時候不是問題直接的拆解，而是轉(zhuǎn)換為關(guān)聯(lián)的問題，然后最優(yōu)解依賴這個關(guān)聯(lián)的問題。
計算最優(yōu)解 這一步一般是根據(jù)遞歸定義的遞推式對子問題逐步求解的過程（有時候也被人稱為狀態(tài)轉(zhuǎn)移方程）
構(gòu)建最終的最優(yōu)解 在最大連續(xù)子數(shù)組問題中，即求第一步構(gòu)造的特征數(shù)的最大值。
最長上升子序列
給定一個數(shù)組A[0,n]，假設(shè)全部由整數(shù)構(gòu)成，求這個數(shù)組中最長單調(diào)上升的子序列的長度。
例如：
數(shù)組 [10,1,9,2,2,3,7,101,18] 它的最長遞增的子序列是 [1,2,3,7,18], 結(jié)果為5
動態(tài)規(guī)劃求解問題最困難的部分在于第一步和第二步：如何刻畫它的問題結(jié)構(gòu)特征，從而建立狀態(tài)轉(zhuǎn)移方程，也就是遞推式。
對于這個問題，我們?nèi)匀谎赜米畲笞有蛄袉栴}中的技巧，構(gòu)造一個以數(shù)組中每個元素作為右界的上升子序列的最長長度的特征數(shù)組 R[0,n] , R[i] 表示以元素A[i], 0 ≤ i < n為右界的上升子序列的最長長度。
顯然，對任意的 0 ≤ i < n, R[i] ≥ 1;
考察 R[i + 1], 如果A[i+1] > A[i], 顯然我們可以將A[i+1]加入到子序列中，將上升子序列的長度擴(kuò)充1,所以 我們得到R[i+1]的一個下界：
R[i + 1] ≥ R[i] + 1
實(shí)際上，對所有小于 0 ≤ j < i + 1的j，只要 A[j] < A[i+1] 都可以得到 類似上面的不等式，
R[i + 1] ≥ R[j] + 1, 0 ≤ j < i + 1 且 A[j] < A[i+1]
因?yàn)锳[j] ≥ A[i+1], A[j]無法加到R[j]的最右邊，這時R[i+1]的一個上界可以在A[0,i]中找出那些小于A[i+1]的數(shù)對應(yīng)的最大的R[j], 0 ≤ j < i + 1
即：
簡單論證一下上面的遞推式， 對每個 0 ≤ j < i + 1 且 A[j] < A[i+1] 上面已經(jīng)論證了 R[j] + 1 是R[i+1]的一個下界。R[ i+1] 必須包含A[i+1]， 所以那些比A[i+1]大的j ( 0 ≤ j < i + 1), 無法加入A[i+1]，所以R[i+1]必在小于A[i+1]的那些R[j]中取，然后拼接A[i+1]。
以上的遞推式（狀態(tài)轉(zhuǎn)移方程）可以逐步計算出所有的R[i] 0 ≤ i < n, 最終我們合成的解就是
max {R[i]} (0≤ i < n)
int length_of_LIS(vector<int>& nums) {
auto n = nums.size();
vector<int> R(n);
R[0] = 1;
for (auto i = 0; i < n; ++i) {
int max_r = 1;
for (auto j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
if (max_r < R[j] + 1)
max_r = R[j] +1;
}
}
R[i] = max_r;
}
return *max_element(R.begin(), R.end());
}
這個算法的時間復(fù)雜度是O(n2) 因?yàn)?，每次尋找最大的R[i]時，需要一個O(n)的時間來查到最大值，能否優(yōu)化這個過程？
偷竊問題
一個小偷去一個村莊偷東西，假設(shè)他不能同時偷相鄰的房屋，否則會觸發(fā)報警系統(tǒng)，已知每個房屋可以偷取的價值，求最優(yōu)偷竊方案。用數(shù)組array[n]表示每個房屋可偷取的最大價值。
例如，[5,2,3]可以選擇偷第1和第3戶，得到最大的總價值為8；
[1,100,3] 選擇偷第2戶，得到的總價值為100；
[1,100,1,3,18] 選擇第2和第5戶，得到總價值為118。
暴力解法的思路：計算所有可能的組合：
考慮一個有10個房屋的序列，我們有兩種方法開始偷竊之旅，從第1間開始，從第2間開始。
不能從第三間開始：因?yàn)閮r值序列是正整數(shù)，這時可以順帶偷竊第1間，將偷竊價值增加。
每次偷完一間房屋，都有兩個選擇繼續(xù)下去，要么隔1間，要么隔2間
最終我們畫出兩棵樹（方便起見，上圖省略了開始的空節(jié)點(diǎn)，實(shí)際上可以整合成一棵樹）每個葉子節(jié)點(diǎn)對應(yīng)一種偷竊路徑。
如果沿著每種路徑求和一次，我們會發(fā)現(xiàn)實(shí)際上會重復(fù)求解，例如圖中的藍(lán)色子樹，實(shí)際上是一樣的。唯一的區(qū)別就是它是從1出發(fā)還是從2出發(fā)。窮舉法會導(dǎo)致重復(fù)問題求解，編碼中體現(xiàn)為反復(fù)對同一組數(shù)求和。
使用動態(tài)規(guī)劃的思路求解。
首先我們要提取一個最優(yōu)解的特征，構(gòu)造子問題：用dp[i]表示偷竊路徑必經(jīng)第i個房屋的偷竊最大值。
dp[i]有兩種方式構(gòu)成，一種是經(jīng)過第i-2個房屋，此時dp[i-2]再加上array[i]就是dp[i];另一種是不經(jīng)過第i-2間房子，那么，因?yàn)槊看瓮蹈`只能隔1間或2間房子，那么不經(jīng)過第i - 2的偷法必然經(jīng)過第 i - 3間房子，這種路徑的最大值可以考慮從dp[i-1] 中減去array[i-1]然后補(bǔ)上array[i]得到，因而得到子問題一個遞推式：
dp[0] = array[0] ;
dp[1] = max(array[0], array[1]}
dp[i] = max{dp[i-2] + array[i], dp[i-1] + array[i] - array[i-1]} i ≥ 2
重構(gòu)最優(yōu)解
注意到，最優(yōu)偷竊選擇要么最后經(jīng)過的房子是最后一間，要么是倒數(shù)第二間，不可能最后兩間屋子都不經(jīng)過，為什么？（不管不經(jīng)過n-1, n-2的偷法有沒有經(jīng)過n-3，我們總是可以選擇n-1或n-2使總價值增加）
所以最終的解:
max_rob = max(dp[n-1], dp[n-2])
int rob(vector<int>& nums) {
if (nums.size() == 1) {
return nums[0];
}
if (nums.size() == 2) {
return max(nums[0], nums[1]);
}
int dp0 = nums[0], dp1 = nums[1];
for (auto i = 2; i < nums.size(); ++i) {
int tmp = dp1;
dp1 = max(nums[i] + dp0, nums[i] - nums[i-1] + dp1);
dp0 = tmp;
}
return max(dp0, dp1);
}
每個階段的最優(yōu)解只依賴前兩個問題的最優(yōu)解，因此只需要維持兩個變量不斷迭代即可，最終算法的時間復(fù)雜度是O(n),空間復(fù)雜度是O(1)
