深入淺出理解動態規劃 | 交疊子問題與最優子結構
歡迎訪問部落客個人網站，記得收藏哦，點擊查看 – – – >>>>
原文鏈接：深入淺出理解動態規劃（一） | 交疊子問題
原文鏈接：深入淺出理解動態規劃（二） | 最優子結構
在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若干個互相聯繫的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴於當前面臨的狀態，又影響以後的發展。當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線．這種把一個問題看作是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有「動態」的含義，稱這種解決多階段決策最優化的過程為動態規劃方法。
本期內容：動態規劃
動態規劃是一種將複雜問題分解成很多子問題並將子問題的求解結果存儲起來避免重複求解的一種演算法。
動態規劃演算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。動態規劃演算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
動態規劃(dynamic programming)是一種演算法設計技術，在20世紀50年代由一位卓越的美國數學家 Richard Bellman所發明的。
一個問題能夠使用動態規劃演算法求解時具有的兩個主要性質：
- 第一，交疊子問題
動態規劃演算法的關鍵在於解決冗餘，這是動態規劃演算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其他的演算法。選擇動態規劃演算法是因為動態規劃演算法在空間上可以承受，而搜索演算法在時間上卻無法承受，所以我們舍空間而取時間
- 第二，最優子結構（最優化原理）
最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。
本期通過比較遞歸法、記憶化搜索演算法和打表演算法的時間複雜度，討論動態規劃的主要性質–交疊的子問題。
1、動態規劃問題中的術語
階段： 把所給求解問題的過程恰當地分成若干個相互聯繫的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
狀態： 狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
無後效性： 我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性 。
決策： 一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多問題中，決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的範圍稱為允許決策集合 。
策略： 由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程，可供選取的策略有一定的範圍限制，這個範圍稱為允許策略集合
2、交疊子問題（或重疊子問題）
同分治法（Divide and Conquer）一樣，動態規劃也是將子問題的求解結果進行合併，其主要用在當子問題需要一次又一次地重複求解時，將子問題的求解結果存儲到一張表中（稱為動態規劃表）以免重複計算。因此當沒有公共的（交疊的、重疊的）子問題時動態規劃演算法並不適用，因為沒有必要將一個不再需要的結果存儲起來。例如，二分搜索（折半查找）就不具有重疊的子問題性質。
我們以下面的遞歸求解斐波那契數列的問題為例子，就會發現有很多子問題一次又一次地被重複求解。
/*求解斐波那契數列的遞歸演算法 */
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
下圖是求解fib(5)的遞歸樹：
從上面的遞歸樹我們可以發現fib(3)被調用了2次。如果我們在第1次計算fib(3)時將fib(3)的結果存儲起來，這樣我們在第2次調用fib(3)時就可以使用先前存儲的值，而不需要再次計算fib(3)了。下面是兩種存儲fib(3)值的方法，這兩種方法都可以重複使用存儲的值：
1、記憶化搜索方法（自頂向下）
說明：所謂頂就是我們要求解的問題，這裡就是fib(n)。
採用這種方法，只需對遞歸程式進行一點小小的修改，即在計算某個值時，先查詢一個表。這個表可以使用數組來實現，初始時把數組的值全部初始為NIL（比如-1或0等值，這個值是計算過程中不會出現的那些值）。任何時候當我們需要求解一個子問題時，我們首先查詢這個表，如果這個表中有我們預先對該子問題求解的結果，則我們直接返回表中的這個值，否則我們就對子問題進行計算，並把計算結果存入這個表中，以便在後續計算中可以重複使用。
下面的程式是求解第n個斐波那契數的記憶化搜索版本：
/* 求解第n個斐波那契數的記憶化搜索程式 */
#include<stdio.h>
#define NIL -1
#define MAX 100
int lookup[MAX]; /* 用數組實現的查找表 */
/* 將查找表初始化為NIL */
void _initialize() {
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}
/* 求解第n個斐波那契數 */
int fib(int n) {
if (lookup[n] == NIL) {/* 如果為NIL,表明第n項沒有求解過 */
if (n <= 1)
lookup[n] = n; /* 求解第n項,並把求解結果存入查找表 */
else
lookup[n] = fib(n - 1) + fib(n - 2);
}
return lookup[n]; /* 如果不為NIL,表明第n項求解過,直接返回 */
}
int main() {
int n = 40;
_initialize();
printf("Fibonacci number is %d ", fib(n));
return 0;
}
2、打表法（自底向上）
用打表法求解一個問題時，使用自底向上的方式進行計算並返回表格中的最後一項。例如，同樣是計算第n個斐波那契數，首先計算fib(0)，然後計算fib(1)，再計算fib(2)，計算fib(3)，直到fib(n)。因此，我們採用的是自底向上的方式逐一建立子問題的求解結果表的。
下面是打表法求解第n個斐波那契數的程式。（所謂打表法，就是把計算結果製成表格，然後列印結果，簡稱打表法，也稱製表法。）
/* 打表法 */
#include<stdio.h>
int fib(int n) {
int f[n + 1];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
int main() {
int n = 9;
printf("Fibonacci number is %d ", fib(n));
return 0;
}
打表法和記憶化搜索法都是把子問題的求解結果存入表格。在記憶化搜索方法中，我們只是在需要時往查詢表中添加記錄，而在打表法中，從第1項記錄開始，所有計算結果一項一項地添加到表中。與打表法不同，記憶化搜索方法無需將所有計算結果添加到查詢表中。
人們往往從時間複雜度和空間複雜度兩個方面來衡量某個演算法的優劣性，但在實際生活中，如果對某個演算法的要求不是特別高，我們一般只考慮演算法的時間複雜度。下面通過比較遞歸法、記憶化搜索方法、打表法在求解第n項斐波那契數時的時間開銷來分析演算法的優劣性。
遞歸方法：
#include<stdio.h>
#include<time.h>
/* 求解斐波那契數列的遞歸演算法 */
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
int n = 40;
clock_t begin, end;
double time_spent;
begin = clock(); /* 開始時間 */
printf("Fibonacci number is %d\n", fib(n));
end = clock(); /* 結束時間 */
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("Time Taken %lf\n", time_spent);
return 0;
}
運行結果：
注意：上面的時間在不同的機器上是不同的
記憶化搜索方法：
/* 求解第n個斐波那契數的記憶化搜索程式 */
#include<stdio.h>
#include<time.h>
#define NIL -1
#define MAX 100
int lookup[MAX]; /* 用數組實現的查找表 */
/* 將查找表初始化為NIL */
void _initialize() {
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}
/* 求解第n個斐波那契數 */
int fib(int n) {
if (lookup[n] == NIL) {/* 如果為NIL,表明第n項沒有求解過 */
if (n <= 1)
lookup[n] = n; /* 求解第n項,並把求解結果存入查找表 */
else
lookup[n] = fib(n - 1) + fib(n - 2);
}
return lookup[n]; /* 如果不為NIL,表明第n項求解過,直接返回 */
}
int main() {
int n = 40;
clock_t begin, end;
double time_spent;
_initialize();
begin = clock(); /* 開始時間 */
printf("Fibonacci number is %d\n", fib(n));
end = clock(); /* 結束時間 */
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("Time Taken %lf\n", time_spent);
return 0;
}
運行結果：
注意：上面的時間在不同的機器上是不同的
打表法：
#include<stdio.h>
#include<time.h>
/* 打表法 */
#include<stdio.h>
int fib(int n) {
int f[n + 1];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
int main() {
int n = 40;
clock_t begin, end;
double time_spent;
begin = clock(); /* 開始時間 */
printf("Fibonacci number is %d\n", fib(n));
end = clock(); /* 結束時間 */
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("Time Taken %lf\n", time_spent);
return 0;
}
運行結果：
注意：上面的時間在不同的機器上是不同的
通過比較三種方法所花費的時間，很明顯遞歸方法比記憶化搜索方法和打表法這兩種採用動態規劃方法所花費的時間都大很多。
3、最優子結構
對於一個給定的問題，當該問題可以由其子問題的最優解獲得時，則該問題具有「最優子結構」性質。
例如，「最短路徑」問題具有如下的「最優子結構」性質：
如果一個結點x在從起點u到終點v的最短路徑上，則從u到v的最短路徑由從u到x的最短路徑和從x到v的最短路徑構成。像Floyd-Warshall（弗洛伊德—沃舍爾）和Bellman-Ford（貝爾曼—福特）演算法就是典型的動態規劃的例子。
另外，「最長路徑」問題不具有「最優子結構」性質。我們這裡所說的最長路徑是兩個節點之間的最長簡單路徑（路徑沒有環），由CLRS（Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein）編寫的《演算法導論》（Introduction to Algorithms）這本書中給出了下面的無權圖。
從q到t有兩條最長的路徑：q→r→t與q→s→t。與最短路徑不同，這些最長路徑沒有「最優子結構」性質。例如，最長路徑q→r→t不是由q 到r的最長路徑和r到t的最長路徑構成的，因為從q到r的最長路徑是 q→s→t→r，從r到t的最長路徑是r→q→s→t。
經典例題：數字三角形
題目描述：
下圖給出了一個數字三角形，從三角形的頂部到底部有很多條不同的路徑，對於每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和。
注意：路徑上的每一步只能從一個數走到下一層上和它最近的左邊的那個數或者右邊的那個數。
輸入：
輸入一個正整數N (1 < N <= 100)，給出三角形的行數，下面的N行給出數字三角形，數字三角形上的數的範圍都在0和100之間。
輸出：
輸出最大的和。
樣例輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
樣例輸出：
30
解題思路：
動態規劃通常用來求最優解。能用動態規劃解決的求最優解問題，必須滿足最優解的每個局部解也都是最優的。以上題為例，最佳路徑中的每個數字到底部的那一段路徑，都是從該數字出發到底部的最佳路徑。
實際上，遞歸的思想在編程時未必要實現為遞歸函數。在上面的例子中，有遞推公式：
不需要寫遞歸函數，從最後一行的元素開始向上逐行遞推，就能求得最終 dp[1][1]的值。程式如下：
#include<stdio.h>
#include<string.h>
#define MAX_NUM 1000
int D[MAX_NUM + 10][MAX_NUM + 10]; /* 存儲數字三角形 */
int N; /* 數字三角形的行數 */
int dp[MAX_NUM + 10][MAX_NUM + 10]; /* 狀態數組 */
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
memset(dp, 0, sizeof(dp));/* 狀態數組全部初始化為0 */
for (i = 1; i <= N; ++i)
for (j = 1; j <= i; ++j)
scanf("%d", &D[i][j]); /* 輸入數字三角形 */
for (j = 1; j <= N; j++) { /* 處理最底層一行 */
dp[N][j] = D[N][j]; /* 最底層一行狀態數組的值即為該數字本身 */
}
for (i = N - 1; i >= 1; i--) { /* 從倒數第二層開始直至最頂層 */
for (j = 1; j <= i; j++) {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1][1]); /* 頂點（1,1）即為最大值 */s
return 0;
}
如下圖所示，方框里的數字是能取得的最大值。相信大家看完這個圖，對動態規劃的理解不那麼困難了。
實際上，因為dp[i][j]的值在用來計算出dp[i-1][j]後已經無用，所以可以將計算出的dp[i-1][j]的值直接存放在dp[i][j]的位置。這樣，計算出 dp[N-1][1]替換原來的 dp[N][1]，計算出 dp[N-1][2]替換原來的dp[N][2]……計算出 dp[N-1][N-1]替換原來的 dp[N][N-1]，dp數組實際上只用最後一行，就能夠存放上面程式中本該存放在dp[N-1]那一行的全部結果。同理，再一行行向上遞推，dp數組只需要最後一行就可以存放全部中間計算結果，最終的結果（本該是dp[1][1])也可以存放在dp[N][1]）。因此，實際上dp不需要是二維數組，一維數組就足夠了。
改寫後的程式如下：
#include<stdio.h>
#include<string.h>
#define MAX_NUM 1000
int D[MAX_NUM + 10][MAX_NUM + 10]; /* 存儲數字三角形 */
int N; /* 數字三角形的行數 */
int *dp; /* 狀態數組 */
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
for (i = 1; i <= N; ++i)
for (j = 1; j <= i; ++j)
scanf("%d", &D[i][j]); /* 輸入數字三角形 */
dp = D[N]; /* dp指向第N行 */
for (i = N - 1; i >= 1; i--) { /* 從倒數第二層開始直至最頂層 */
for (j = 1; j <= i; j++) {
dp[j] = max(dp[j], dp[j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1]); /* （1,1）即為最大值 */
return 0;
}
這種用一維數組取代二維數組進行遞推、節省空間的技巧叫「滾動數組」。上面的程式雖然節省了空間，但是沒有降低時間複雜度，時間複雜度依然是O(N^2)的，從程式使用了兩重循環就可以看出。
4、總結
許多求最優解的問題可以用動態規劃來解決。用動態規劃解題，首先要把原問題分解為若干個子問題，這一點和前面的遞歸方法類似。區別在於，單純的遞歸往往會導致子問題被重複計算，而用動態規劃的方法，子問題的解一旦求出就會被保存，所以每個子問題只需求解一次。
子問題經常和原問題形式相似，有時甚至完全一樣，只不過規模從原來的n變成n-1, 或從原來的n×m變成n×（m-1）。找到子問題，就意味著找到了將整個問題逐漸分解的辦法，因為子問題可以用相同的思路一直分解下去，直到最底層規模最小的子問題可以一目了然地看出解（像上面數字三角形的遞推公式中，當i=N時，解就可以直接得到）。每一層子問題的解決會導致上一層子問題的解決，逐層向上，就會導致最終整個問題的解決。如果從最底層的子問題開始，自底向上地推導出一個個子問題的解，那麼編程時就不需要寫遞歸函數了。
5、文章推薦
推薦一：深入淺出理解動態規劃（一） | 交疊子問題,文章內容：動態規劃–交疊子問題（記憶化搜索演算法、打表法求解第n個斐波那契數）。
推薦二：深入淺出理解動態規劃（二） | 最優子結構,文章內容：動態規劃–最優子結構（經典例題：數字三角形求解）。
6、公眾號推薦（資源加油站）
了解更多資源請關注個人公眾號：C you again,你將收穫以下資源
1、PPT模板免費下載，簡歷模板免費下載
2、基於web的機票預訂系統，基於web的圖書管理系統
3、貪吃蛇小遊戲源碼
4、各類IT技術分享
