前言

在學習動態規劃時切忌望文生義，因為其名字與其思想關系不大，你可以自己想一個記住其思想的名字，例如：遞推公式法，狀態轉移方程法等等。與其說動態規劃是一個算法，還不如說是解決問題的方法論，動態規劃的一般形式就是求最優值，比如最長公共子序列，最大子段和，最優二叉搜索樹等等。

貪心算法：在前面我們提到過的Prim算法和Kruskal算法就借用到了貪心算法的思想，例如我們的Prim算法，每次我們都選擇選中的頂點中的邊的最小值，但是有一定的條件：選擇出來的邊不能閉環，像這種前一步的貪心和后一步的貪心沒有直接關系就比較簡單一點，例如一個序列中找最大值，最小值。

分治算法：大問題拆分成小問題，小問題之間相對獨立，每個小問題解決方案是一樣的

動態規劃：大問題拆分成小問題，小問題之間互相依賴重復，每個小問題解決方案是一樣的。

1.基本思想

動態規劃算法與分治法類似，其基本思想就是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

與分治法不同的是，適合動態規劃法求解的問題，經分解得到的子問題往往不是相互獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，以至于最后解決原問題需要耗費指數時間。然而，不同子問題的數目常常只有多項式量級。

在用分治法求解時，有些子問題被重復結算了很多次。如果我們能夠保存已經解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，從而得到多項式時間復雜度的算法。為了達到此目的，可以用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃的基本思想。

基本要點：將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解；經分解得到的子問題往往不是相互獨立的；保存已經解決的子問題的答案，避免重復計算。

例如下圖我們想要f(N)的數據，假設需要知道f(x)和f(y)，f(x)需要從f(x1)得知，f(y)需要從f(x2)得知，而f(x2)和f(x1)有關，那我們就可以采用動態規劃的思想，把f(x1)計算出的結果保存下來，這樣計算f(x2)的時候就可以少計算一次f(x1)。

2.重疊子問題

在用遞歸算法自頂向下解決一個問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態規劃正是利用了這種子問題的重疊性質，對每個子問題只解一次，而后將其解保存到一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。

動態規劃經分解得到的子問題往往不是相互獨立的 。如果經分解得到的子問題的解之間相互獨立，比如二分查找（Binary Search）經分解得到的子問題之間相互獨立，不存在重疊子問題，所以不適合用動態規劃，更適合分治算法。

接下來來看一個非常經典的重疊子問題：斐波那契數列。

3.斐波那契數列

我們可以理解斐波那契數列為:f(n)=f(n-1)+f(n-2)（遞推公式）。一個數字等于前面兩個數字的和，這就是一個大問題拆分成幾個小問題，我們需要把它拆分成遞歸搜索樹。

如圖，如果我們想知道斐波那契數列中的第5個數字，我們需要知道第3個和第4個數字，一次向下類推可以得到一顆二叉樹，明顯到當我們拆分到2的時候，我們向下再拆一次就變成了需要知道0和1的問題，此時無法再向下拆分，我們就認為，0和1是初始狀態（你也可以認為是1和2），當我們計算從下往上運算的時候，如果我們不保存已經計算得到的結果的話，我們會大量重復的計算，例如：先看5的左子樹我們通過計算0，1計算2，再通過2，1計算3，此時3的右邊2我們還需要重復計算，因為我們沒有保存第一次計算得到的2的數值，同理當我們計算到4的時候，我們還需要計算得到5的右子樹的3，因為我們沒有保存第一次計算3時得到的數值，接下來看一看如果我們不保存值的話的時間長短。

這就是一個很簡單的遞歸代碼，我就不過多敘述

#include <stdio.h>
#include <time.h>
#include <stdlib.h>unsigned int fib01(unsigned int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return fib01(n - 1) + fib01(n - 2);
}// 1 1 2 3 5
void test01() {clock_t start = clock();unsigned int x = fib01(40);clock_t end = clock();printf("cost time: %f s。fib01 = %u\n", (double)(end - start) / CLOCKS_PER_SEC, x);
}int main() {test01();return 0;
}

結果：

D:\work\DataStruct\cmake-build-debug\06_DP\fib.exe
cost time: 0.504000 s。fib01 = 102334155進程已結束，退出代碼為 0

現在將數字改為46

#include <stdio.h>
#include <time.h>
#include <stdlib.h>unsigned int fib01(unsigned int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return fib01(n - 1) + fib01(n - 2);
}// 1 1 2 3 5
void test01() {clock_t start = clock();unsigned int x = fib01(46);clock_t end = clock();printf("cost time: %f s。fib01 = %u\n", (double)(end - start) / CLOCKS_PER_SEC, x);
}int main() {test01();return 0;
}

結果：

D:\work\DataStruct\cmake-build-debug\06_DP\fib.exe
cost time: 8.964000 s。fib01 = 1836311903進程已結束，退出代碼為 0

可以看到僅僅只是增加了6個數字，時間一下子增加了8秒之多，這是因為，我們每增加一個，都會多重復計算兩層的數字，時間復雜度近似于n²。

我們有兩種方法解決這種問題，第一種是備忘錄（記憶化搜索表），第二種是DP table，第一種方法是把大問題拆分成小問題，自頂向下解決問題，而第二種方法是拿到一個大問題，先想有哪些小問題需要我們解決，是自底向上解決問題。兩種方法的時間復雜度都差不多，但第一種思路顯然更符合人類的思考方式，所以如果是競賽的同學多考慮第一種方法。

4.備忘錄（記憶化搜索表）

備忘錄方法為每一個子問題建立一個記錄項，初始時，該記錄項存入一個特殊的值，表示該子問題尚未被解決（比如斐波那契數的備忘錄版本中將其設置為-1）。

在求解過程中，對每個待求解的子問題，首先查看其相應的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該子問題是第一次遇到，此時計算出該子問題的解，并保存在相應的記錄項中，以備以后查看。若記錄項中存儲的已不是初始化時存入的特殊值，則表示該子問題已被計算過，其相應的記錄項存儲的是該子問題的答 案。此時，只要從記錄項中取出該子問題的答案即可，而不必重新計算。

4.1備忘錄（記憶化搜索表）代碼實現

#include <stdio.h>
#include <time.h>
#include <stdlib.h>// mem1[i] 記憶了第i個斐波那契數列的值
static unsigned int *mem1;
unsigned int fib02(unsigned int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}if (mem1[n] == -1) {mem1[n] = fib02(n - 1) + fib02(n - 2);}return mem1[n];
}void test02() {int n = 46;mem1 = malloc(sizeof(unsigned int) * (n + 1));// 初始化這個表里，存儲一個以后算法中永遠不會出現的狀態for (int i = 0; i <= n; ++i) {mem1[i] = -1;		}clock_t start = clock();unsigned int x = fib02(n);clock_t end = clock();printf("cost time: %f s。fib02 = %u\n", (double)(end - start) / CLOCKS_PER_SEC, x);free(mem1);
}

結果：

D:\work\DataStruct\cmake-build-debug\06_DP\fib.exe
cost time: 0.000000 s。fib02 = 1836311903進程已結束，退出代碼為 0

可以看到，用的時間極短，我們存儲了已經計過的值后，當遇到相同的值時我們直接返回就行不再需要重復計算，這大大減少了遞歸搜索樹的節點，所以時間效率很高。

5.DP table

DP table就是動態規劃算法自底向上建立的一個表格，用于保存每一個子問題的解，并返回表中的最后一個解。比如斐波那契數，我們先計算 fib(0)，然后 fib(1)，然后 fib(2)，然后 fib(3)，以此類推，直至計算出fib(n)。

比如我們計算 fib(5)，先由 fib(0) + fib(1) 得到 fib(2)，再由 fib(1) + fib(2) 得到 fib(3)，再由 fib(2) + fib(3) 得到 fib(4)，最后由 fib(3) + fib(4) 得到 fib(5)。

也就是說，我們只需要存儲子問題的解，而不需要重復計算子問題的解。

5.1DP table代碼實現

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
unsigned int fib03(unsigned int n) {unsigned int *mem = malloc(sizeof(unsigned int) * (n + 1));//遞推mem[0] = 0;mem[1] = 1;for (int i = 2; i <= n; ++i) {mem[i] = mem[i - 1] + mem[i - 2];}unsigned int result = mem[n];free(mem);return result;
}void test03() {int n = 146;clock_t start = clock();unsigned int x = fib03(n);clock_t end = clock();printf("cost time: %f s。fib03 = %u\n", (double)(end - start) / CLOCKS_PER_SEC, x);
}int main() {test03();return 0;
}

D:\work\DataStruct\cmake-build-debug\06_DP\fib.exe
cost time: 0.000000 s。fib03 = 2620762145進程已結束，退出代碼為 0

可以看到即使數字變成了146，我們的時間效率還是很高，因為我們已經保存了很多節點的數字。

6.練習

問題描述：給定三個數{1，3，5}，請問使用這三個數，有多少種方式可以構造出一個給定的數n（假設這里n等于6）（允許重復和不同順序）

如圖，這個題的遞歸搜索樹大致如圖，我沒有畫完全，大致能懂意思就行。

我們可以先寫出遞歸的函數：

int combine01(int n) {if (n < 0) {return 0;}if (n == 1 || n == 0) {return 1;}return combine01(n - 1) + combine01(n - 3) + combine01(n - 5);
}

當n小于0的時候很明顯沒有組合方式，當n等于1或者n等于0的時候只有一種組合方式。

1. 最后一步采用操作1（步長為1）
   如果最后一步是操作1，那么在此之前需要解決規模為 n-1 的問題

所以有 combine01(n-1) 種方式

2. 最后一步采用操作3（步長為3）
   如果最后一步是操作3，那么在此之前需要解決規模為 n-3 的問題

所以有 combine01(n-3) 種方式

3. 最后一步采用操作5（步長為5）
   如果最后一步是操作5，那么在此之前需要解決規模為 n-5 的問題

所以有 combine01(n-5) 種方式

總和起來就是我們所有的方法數，接下來先采用今天講的備忘錄（記憶化搜索表）實現：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
static int solve(int n, int *mem) {if (n < 0) {return 0;}if (n == 1 || n == 0) {return 1;}if (mem[n] == -1) {mem[n] = solve(n - 1, mem) + solve(n - 3, mem) + solve(n - 5, mem);}return mem[n];
}int combine02(int n) {int result;int *mem = malloc(sizeof(int) * (n + 1));for (int i = 0; i <= n; ++i) {mem[i] = -1;}result = solve(n, mem);free(mem);return result;
}int main() {printf("%d\n", combine03(6));return 0;
}

結果：

D:\work\DataStruct\cmake-build-debug\06_DP\cunNum.exe
8進程已結束，退出代碼為 0

再來用DP table的方法：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
static int solve(int n, int *mem) {if (n < 0) {return 0;}if (n == 1 || n == 0) {return 1;}if (mem[n] == -1) {mem[n] = solve(n - 1, mem) + solve(n - 3, mem) + solve(n - 5, mem);}return mem[n];
}
int combine03(int n) {int *mem = malloc(sizeof(int) * (n + 1));mem[1] = 1;mem[2] = 1;mem[3] = 2;mem[4] = 3;mem[5] = 5;for (int i = 6; i <= n; ++i) {mem[i] = mem[i - 1] + mem[i - 3] + mem[i - 5];}int result = mem[n];free(mem);return result;
}int main() {printf("%d\n", combine03(6));return 0;

結果：

D:\work\DataStruct\cmake-build-debug\06_DP\cunNum.exe
8進程已結束，退出代碼為 0

大家可以在LeetCode刷類似的題目，大概先寫這些吧，今天的博客就先寫到這，謝謝您的觀看。