動態規劃 · 算法

[TOC] # 參考資料 [知乎：什么是動態規劃？](http://www.zhihu.com/question/23995189) [百度百科：動態規劃](http://baike.baidu.com/link?url=vGpz96tU-DsVSn91-qJK1NC9MrlwSi3TW9A_Cx6O6ReHSMX4mjP8EmsoR2Rgb1pF9yNDPbFilyKjIax2doSqUq) [維基百科：動態規劃](https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92) 每個階段只有一個狀態->遞推；每個階段的最優狀態都是由上一個階段的最優狀態得到的->貪心；每個階段的最優狀態是由之前所有階段的狀態的組合得到的->搜索；每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到而不管之前這個狀態是如何得到的->動態規劃。 # Introduction Dynamic Programming is to solve combinatorial optimization problems,where we are looking for the best possible input to some function chosen from an exponentially large search space. There are two part about DP. *The first part is* programming technique:DP is essentially divide and conquer run in reverse:we solve a big instance of a problem by breaking it up recursively into smaller instances;but instead of carrying out the computation recursicely from the top down,we **start from the bottom with the smallest instances of the problem,solving each increasingly large instance in turn and storing the result in a table.** *The second part is* design principle:in building up our table,we are careful always preserve alternative solutions we may need later,by delaying commitment to particular choices to the extent that we can. * * * * * 因為動態規劃解決的問題主要是組合最優解問題。對于分治，上一種狀態和下一種狀態沒有過多的聯系，我們主要考慮上一種唯一狀態的返回結果就好，（n! = n*(n-1)!）。但對于動態規劃來說，它需要將前幾種狀態綜合進行考慮，然后得出下一種狀態的最優解。那么，動態規劃需要考慮倆點，一是最優子結構，一是重疊子問題。 * overlappings subproblems - memoization * Table look-up * Optional substructure:global optional sultion can be constructed from optional solvtions to sub-problems ### Memoization ``` int memoFib(int n) { int ret; if(hashContains(FibHash,n)) { return hashGet(FibHash,n); } else { ret = memoFib(n-1) + memoFib(n-2); hashPut(FibHash,n,ret); return ret; } } ``` # 動態規劃和分治動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣，但它們具有相同的填表格式。 # Bottom-up and Top-down Bottom-up：由簡單到復雜，一般用迭代 Top-down：由復雜到簡單，一般用遞歸 # 斐波那契數列 ### 斐波那契數列的定義 > F(n) = F(n-1)+F(n-2),n>1;F(0) = 1;F(1) = 1; ### 最差遞歸實現 ``` int f(int n) { if(n <= 1) return 1; return f(n-1) + f(n-2); } ``` #### 為什么不好？ ![](https://box.kancloud.cn/2016-04-08_57077fb5c89ce.PNG) ![](https://box.kancloud.cn/2016-04-09_5708778c28b34.PNG) 1. 遞歸調用過程中會出現很多重復計算的步驟。(因為遞歸樹的原因)。如在計算f(4)的時候要計算f(3)和f(2)，而這里的值不會被保存下來，所以，f(3)中對f(2)仍然要計算一次。它的算法時間復雜度為O(a^n),a=1.628... 2. 遞歸調用會出現棧溢出的危險，它的空間復雜度也會隨著n值的擴大而指數級增長。 ### 改進版本1 ``` int f(int n) { int f0 = f1 = ret = 1; int i; for(i=1,i<n-1;i++) { ret = f0+f1; f0 = f1; ret = f1; } return ret; } ``` 計算過程如下： | n | 0 |1|2|3|...| | -- | -- |--|--|--| | f0 | 1|1|1|2|...| | f1 | 1|1|2|3|...| | ret | 1|2|3|5|...| ### 改進版本2 ``` int f(int n) { int *a = (int *)malloc(sizeof(int)*(n+1)); int i,ret; a[0] = a[1] = 1; for(i=2;i<n+1;i++) a[i] = a[i-1]+a[i-2]; ret = a[i]; free(a); reutrn ret; } ``` ### 改進版本3 利用Memoization來實現 ``` //不太好，因為此處需要申明一個全局變量的數組。 #define SIZE (100) int FibHash[SIZE] = {0}; int hashContains(FibHash,n) { if(n>=2 && FibHash[n] == 0) return 0; return 1; } int hashGet(FibHash,n) { return FibHash[n]; } void hashPut(FibHash,n,ret) { FibHash[n] = ret; } int memoFib(int n) { int ret; if(hashContains(FibHash,n)) { return hashGet(FibHash,n); } else { ret = memoFib(n-1) + memoFib(n-2); hashPut(FibHash,n,ret); return ret; } } ``` # 1，3，5元面值若干，湊錢問題 ### 算法思想假如要計算11元需要的面值數最小，那么，11元減去一張1元或者3元或者5元，即10元，8元，6元分別需要的面值數，取出最小，加上1，即可以得到11元最小的。所以，n元最小問題，是由n-1元，n-3元，n-5元三種狀態里面取到的最優解。其中計算的遞歸樹為： ![](https://box.kancloud.cn/2016-04-08_57078535aed08.png) d(11) = min{d(10),d(8),d(6)} + 1 ### 遞推式 > d(i) = min{d(i-v)} + 1,其中v為面值1，3，5；i為求值 ### 實現代碼版本-1 ``` #include <stdio.h> # #define AA (1) #define BB (3) #define CC (5) # //min int min(int m,int n,int p) { int ret = p; if(ret > m) ret = m; if(ret > n) ret = n; return ret; } //主函數 int myAnswer(int y) { int *a = (int *)malloc(sizeof(int)*(y+1)); int i,ret; a[0] = 0; for(i=1;i<y+1;i++) { a[i] = min(a[i-AA],((i-BB)>=0) ? a[i-BB] : 0,((i-CC)>=0) ? a[i-CC] : 0)+1; } ret = a[y]; free(a); return ret; } int main(int argc,char **argv) { int answer = myAnswer(11); printf("answer is %d",answer); return 0; } ``` # 最長非遞減子序列（longest increasing subsequence） ### 算法思想 Suppose that we want to compute the Longest increasing Subsequence of an array.This is a sequence,not necessarily contiguous,of elements from the array such that each is strictly larger than the one before it.Since there are 2^n different subsequences of an n-element array,the brute-force approach of trying all of them might take a while. *** 假設有一個序列： 3 2 4 5 6 7 9 2 *d(1) = 1;(3) d(2) = 1;(2) d(3) = max{d(1),d(2)} +1 = 2;(4) d(4) = max{d(1),d(2),d(3)}+1 = 3;(5) d(5) = max{d(1),d(2),d(3),d(4)}+1 = 4;(6) d(6) = max{d(1),d(2),d(3),d(4),d(5)}+1 = 5;(7) d(7) = max{d(1),d(2),d(3),d(4),d(5),d(6)}+1 = 6;(9) d(8) = max{d(2)}+1 = 2;(2)* ### 遞推式（狀態轉移方程） > d(i) = max{d(j)} + 1; a[i] >= a[j] ### 實現代碼版本-1 ``` #include <stdio.h> int Lis(int *A,int n) { int d[n]; int i,j; int sum = 0; int ret = 1; if(n == 1) return ret; for(i=0;i<n;i++) { d[i] = 0; //printf("%d\n",A[i]); for(j=0;j<i;j++) { if(A[j]<A[i] && d[j] > sum) { sum = d[j]; } } d[i]=sum+1; sum = 0; if(d[i] > ret) ret = d[i]; } return ret; } int main(int argc,char *argv[]) { int A[] = {3,2,4,5,6,9,7,3,3,10}; int b = Lis(A,10); printf("%d",b); } ``` ### 實現代碼版本-2 ``` #include <stdio.h> #include <assert.h> unsigned long longest_increasing_sub(const int a[],unsigned long n,int *output) { struct lis_data { unsigned long length; unsigned long prev; }*table; unsigned long best; unsigned long scan; unsigned long i; unsigned long j; unsigned long best_length; if(n == 0) return 0; table = (struct lis_data *)malloc(sizeof(*table)*n); for(i=0;i<n;i++) { table[i].length = 1; table[i].prev = n; for(j=0;j<i;j++) { if(a[j]<a[i] && table[j].length+1 > table[i].length) { table[i].length = table[j].length+1; table[i].prev = j; //上一個子LIS的下標 } } } best = 0; for(i=1;i<n;i++) { if(table[i].length > table[best].length) { best = i; } } best_length = table[best].length; if(output) { scan = best; for(i=0;i<best_length;i++) { assert(scan >=0); assert(scan < n); output[best_length-i-1] = a[scan]; scan = table[scan].prev; } } free(table); return best_length; } int main() { int a[] = {2,12,3,4,5,6,4,2,2,12,4,56,8,42,100}; int n = 15; int i; int output[15] = {0}; int best = longest_increasing_sub(a,n,output); for(i=0;i<best;i++){ printf("%d ",output[i]); } printf("\nbest_length is %d",best); } ``` # 最長公共子序列（Longest Common Subsequence） ### 算法思想 ![](https://box.kancloud.cn/2016-04-09_5708c87ed7eb2.PNG) ### 遞推式 ![](https://box.kancloud.cn/2016-04-09_5708730f9b8e9.jpg) ### 實現代碼版本-1 ``` #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include <limits.h> void LCS(const char *x,const char *y,char *lcs) { int xLen; int yLen; int i; int j; xLen = strlen(x); yLen = strlen(y); struct choice { int length; struct choice *prev; char newChar; }best[xLen][yLen]; for(i = 0;i < xLen;i++) { for(j = 0;j<yLen;j++) { best[i][j].length = 0; best[i][j].prev = 0; best[i][j].newChar = 0; if(x[i] == y[j]) { best[i][j].newChar = x[i]; if(i>0 && j>0) { best[i][j].length = best[i-1][j-1].length+1; best[i][j].prev = &best[i-1][j-1]; } else { best[i][j].length = 1; } } if(i>0 && best[i-1][j].length > best[i][j].length) { best[i][j].length = best[i-1][j].length; best[i][j].prev = &best[i-1][j]; best[i][j].newChar = 0; } if(j>0 && best[i][j-1].length > best[i][j].length) { best[i][j].length = best[i][j-1].length; best[i][j].prev = &best[i][j-1]; best[i][j].newChar = 0; } } } int outPos; struct choice *p; outPos = best[xLen-1][yLen-1].length; //printf("%d",outPos); lcs[outPos--] = '\0'; for(p = &best[xLen-1][yLen-1] ; p ; p = p->prev) { if(p->newChar) { assert(outPos >= 0); lcs[outPos--] = p->newChar; } } } int main(int argc,char **argv) { if(argc != 3) { fprintf(stderr,"%s",argv[0]); return 1; } // printf("%s%s%s",argv[0],argv[1],argv[2]); char output[strlen(argv[1])+1]; LCS(argv[1],argv[2],output); puts(output); return 0; } ``` # 0-1背包問題（編程導論13集） ### 算法思想 ![](https://box.kancloud.cn/2016-04-09_5708ce379f9d1.jpg) #### 基于決策樹的直觀解法 W = [5,3,2] V = [9,7,8];MAX = 5 Descion tree: ### 遞推式 > F[i,j] = max{F[i-1,j],F[i-1,j-wi]+pi},j-w>=0 ### 實現代碼版本-1 ``` /** * 背包問題：weight=[3,4,5] * value=[4,5,6] * max = 10 * * d[i][j] = max(d[i-1][j],d[i-1][j-w]+v) * * * */ #include <stdio.h> int pack(int w[],int v[],int n,int max) { max++; int i,j; int A[n][max]; int with=0; int without = 0; int maxValue = 0; for(j=0;j<max;j++) { for(i=0;i<n;i++) { A[i][j] = 0; if(i == 0 && j-w[i]>=0) A[i][j] = v[i]; if(i-1>=0) without = A[i-1][j]; if(i-1>=0 && j-w[i]>=0) with = A[i-1][j-w[i]]+v[i]; //A[i][j] = with>without ? with : without; if(A[i][j]<with) A[i][j] = with; if(A[i][j]<without) A[i][j] = without; if(A[i][j]>=maxValue) maxValue = A[i][j]; } } /* for(j=0;j<max;j++) { for(i=0;i<n;i++) { printf("%d ",A[i][j]); } printf("\n"); } */ return maxValue; } int main(int argc,char **argv) { int w[] = {3,4,5,6}; int v[] = {4,5,6,7}; int max = 13; int n = 4; int maxValue = 0; maxValue = pack(w,v,n,max); printf("%d",maxValue); } ``` # 最大子段和 ### 算法思想 ### 遞推式 ![](https://box.kancloud.cn/2016-04-09_570854887560d.jpg) > b[i] = max {a[i] , b[i-1]+a[i]}，取最大的b[i] ### 實現代碼版本-1 ``` #include <stdio.h> int MSS(int a[],int n) { int *b = (int *)malloc(sizeof(int) * n); b[0] = a[0]; int i=0,sum=b[0]; for(i=1;i<n;i++) { b[i] = b[i-1]>0 ? (b[i-1]+a[i]) : a[i]; if(b[i]>sum) sum = b[i]; } return sum; } int main() { int a[] = {3,5,-2,9,10,1}; int c = MSS(a,6); printf("%d",c); } ``` # 最長對稱子序列 ### 代碼版本-1 ``` #include <stdio.h> int main(void) { char str[100]; gets(str); int b[100]; int i,j1,j2; int max = 1; b[0] = 1; if(str[0] == str[1]) b[1] = 2; else b[1] = 1; for(i=2;i<strlen(str);i++) { b[i] = 1; j1 = i-1; j2 = i-b[i-1]-1; if(str[j1] == str[i]) b[i] = 2; if(str[j2] == str[i]) b[i] = b[i-1]+2; if(max < b[i]) max = b[i]; } printf("%d",max); return 0; } ``` ### 代碼版本-2 ``` #include <stdio.h> int main(void) { char str[100]; gets(str); int b[100]; int i,j1,j2,j3; int max = 1; b[0] = 1; if(str[0] == str[1]) b[1] = 2; else b[1] = 1; for(i=2;i<strlen(str);i++) { b[i] = 1; j1 = i-1; j2 = i-b[i-1]-1; j3 = i-2; if(str[j2] == str[i]) b[i] = b[i-1]+2; else if(str[j3] == str[i]) b[i] = 3; else if(str[j1] == str[i]) b[i] = 2; if(max < b[i]) max = b[i]; } printf("%d",max); return 0; } ``` # 矩陣連乘問題 # 凸多邊形最優三角剖分 # 多邊形游戲 # 圖像壓縮 # 電路布線 # 流水作業調度 # 最優二叉搜索樹