前言

這一強大的算法卻有一個不相關的名字，常常引起混淆。實際上創造者Richard Bellman把這名字作為保護傘來掩人耳目的，從此延續下來。說它強大是因為應用范圍很廣，在優化算法中，在圖像融合中，在很多實際問題中都有其身影。還因為使用它往往能收到奇效，當你嘗試了分治，嘗試了貪心仍然不能滿意的時候也許動態規劃才是最好的選擇。這么好的方法想從心所欲并非易事，甚至很多時候無從下手。像動態規劃算法本身所做的那樣，我們把大事化小，小事化了，循序漸進的掌握它。

動態規劃三部曲

• 大問題分解成子問題
• 從子問題分析狀態和狀態轉移方程
• 自底向上的實現

和分治一樣的地方是把大的化小，不一樣的是在動態規劃中小問題與原問題的本質相同，并且小問題的規模減少的不多，不是分治期望的一半。這樣一來如果應用分治算法會大量的計算重復子問題導致十分緩慢，在動態規劃中把這些小問題的結果存儲下來不斷的調用，這也是為什么要自底向上實現的原因。難就難在了第二部分，怎樣分析出狀態和狀態轉移方程，讓我們結合具體的例子來理解。

動態規劃4例

1.湊硬幣????????說我們有面值為1,3,5的硬幣若干，問湊夠11元所需最少硬幣數。

三部曲之一，大化小。假如把湊夠11元看成一個大問題，那么小問題是什么？湊夠10元？9元？。。。或者說湊夠i元。小問題浮出水面，湊夠i元所需最少硬幣就是原問題的子問題，這一子問題與原問題是同質的。換一個角度來看，如果這個子問題你解決了，那么原問題或者和原問題相當的問題你都解決了，說白了你解決的是一類問題。什么湊夠888元，999元都不在話下。

三部曲之二，由子問題到狀態和狀態轉移方程。狀態就是子問題的數學表達，借助于數學符號易于發現其中規律。d[i]=j，表示湊夠i元最少需要j個硬幣。那么好了，從最簡單的情況開始，通過歸納和對比看看能不能找出什么規律來。d[0]=?，換句話說湊夠0最少需要多少硬幣，當然是0個了，所以d[0]=0。也不難發現d[1]=d[1-1]+1=1，d[2]=d[2-1]+1=2。d[3]的時候就有所不同了，當然我們都知道d[3]=1，就是湊夠3最少需要1個硬幣。那么這個1是怎么來的？放慢思維會發現，首先試圖用面值1元的需要3個，然后用面值3元的需要1個，面值5元的我們智慧大腦果斷放棄了。在照顧到所有情況以后，得到結果d[3]=min(d[3-1]+1,d[3-3]+1)=1。把d[0]，d[1]，d[2]，d[3]寫成更一般的形式d[i]=min(d[i-v[j]]+1)，i>v[j]（j表示第j個硬幣，v[j]表示第j個硬幣的面值）。d[i]=min(d[i-v[j]]+1)，i>v[j]就是狀態轉移方程，描述狀態之間的轉化關系。

三部曲之三，自底向下實現，有了狀態和狀態轉移方程實現順其自然，需要留意的地方是初始狀態，它是已知的，通常是0或者無窮大，或者無窮小。

/**湊硬幣 輸入：現有面值1,3,5,7 的硬幣若干 輸出：如何用最少的硬幣湊夠S元，比如說11元。 狀態：d[i]表示湊夠i所用的最少硬幣 狀態轉移方程：d[i] =min(d[i-v[j]]+1), v[j]<=i (v[j]表示第j個硬幣的面值) */ void coin_assmbling() {const int Money = 11;vector<int> value = {1,3,5,7};vector<int> d(Money + 1, Infinity);d[0] = 0;for (int i = 1; i < Money + 1; ++i)for (int j = 0; j < value.size();++j){if (value[j] <= i && d[i] > d[i - value[j]] + 1){d[i] = d[i - value[j]] + 1;}}cout << "min coin num: " << d[Money] << endl; }

2.最長非降子序列的長度????????[5，3，4，8，6，7]的最長非降子序列是3，4，6，7長度是4

還是原來的步驟，還是原來的方法。子問題？[5，3，4，8，6]是原序列的子序列，[5，3，4，8]也是。那么用A[i]表示以第i個元素結尾的序列，A[i]的最長非降子序列就是原問題的一個子問題。求出所有A[i]的最長非降子序列，其中最最長的就是最終的結果。用d[i]表示以第i個元素結尾的最長非降子序列，從易到難。

• 前一個數的LIS：d[1]=1（序列5）
• 前兩個數的LIS：d[2]=1（序列5，3，3前面沒有比3小的）
• 前三個數的LIS：d[3]=2（序列5，3，4；4前有3所以d[3]=d[2]+1）
• 前4個數的LIS：d[4]=3（序列5，3，4，8；d[4]=max(d[1],d[2],d[3]+1)）

有上面分析得到狀態轉移方程d[i]=max(1，d[j]+1) j<i，a[j]<=a[i]。文字表述就是把i前面的各個子序列中，最后一個不大于a[i]的數加1，其中的最大值就是所求。當然有可能每個子序列都大于a[i]，比如[5，4，3，2，1]的最長非降子序列是1。

/**最長非降子序列（LIS） 輸入：數組 a 輸出：最長非降子序列的長度及其內容 狀態：d[i]表示以a[i]結尾的最長非降子序列的長度 狀態轉移方程：d[i]={max(1,d[j+1]), j<i a[j]<=a[i]} */ void longest_increasing_subsequence() {vector<int> a = { -2, 11, -4, 13, -5, -2 };vector<int> d(a.size(), 1);d[0] = 1;int max = d[0];int max_id = 0;for (int i = 1; i < a.size();++i){for (int j = 0; j < i;++j){if (a[j] <= a[i] && d[i] < d[j] + 1)d[i] = d[j] + 1;}if (max < d[i]){max = d[i];max_id = i;}}// print max length cout << "max length is: " << max << endl;// print subsequence elementcout << "they are: " << endl;cout << a[max_id] << "\t";int temp = max;for (int i = max_id-1; i >= 0;--i){if (d[i] == temp - 1){cout << a[i] << "\t";temp -= 1;}}cout << endl; }

3.最長公共子序列????比如度量兩個DNA序列的相似程度。

這比上面的例子更復雜，它是2維的動態規劃問題。因為需要兩個變量來刻畫狀態。還是先找出子問題。考慮到兩個序列的子序列可以分別表示成A[i]和B[j]，自然聯想d[i][j]表示以i結尾的序列A[i]和以j結尾的序列B[j]他們最長公共子序列的長度。考慮d[i][j]和它前面狀態d[i-1][j]，d[i][j-1]，d[i-1][j-1]之間的關系。容易得到狀態轉移方程

d[i][j]={0，i==0||j==0; d[i-1][j-1]+1，a[i]==b[j]; max(d[i-1][j],d[i][j-1])，a[]!=b[j];}

/**最長公共子序列（LCS） 輸入：兩個數組 a b 輸出：求他們的最長公共子序列 分析：1.首先把大問題變成小問題，把原問題轉化成求兩個不完全數組的公共子序列，求以分別以a[i]和b[j]結尾的子數組的最長公共子序列。2.從子問題分析狀態，s[i][j]表示a[i] b[j]結尾的子數組的最長公共子序列。進一步分析前一狀態和后一狀態之間的關系。 狀態：s[i][j] 狀態轉移方程：d[i][j]={0 i==0|| j==0; d[i-1][j-1]+1 a[i]==b[j]; max(d[i-1][j],d[i][j-1], a[i]!=b[j]);} */ void longest_common_subsequence() {const string a = { 'A', 'B', 'C', 'B', 'D', 'A', 'B' };const string b = { 'B', 'D', 'C', 'B', 'A' };vector<vector<int>> d(a.size()+1);for (auto& e:d){e.resize(b.size()+1);}vector<vector<int>> table(d);for (int i =0 ; i < a.size();++i){for (int j = 0; j < b.size();++j){if (a[i] == b[j]){d[i + 1][j + 1] = d[i][j]+1;table[i + 1][j + 1] = 0;}else if (d[i][j + 1]>d[i + 1][j]){d[i + 1][j + 1] = d[i][j + 1];table[i + 1][j + 1] = 1;}else{d[i + 1][j + 1] = d[i+1][j];table[i + 1][j + 1] = 2;}}}cout << "longest common subsequence: " << d[a.size()][b.size()]<<endl;cout << "they are: " << endl;int r = a.size();int c = b.size();for (int i = a.size()-1; i>=0; --i){if (table[r][c] == 0){cout << a[r - 1] << "\t";r -= 1;c -= 1;}else if (table[r][c] == 1){r -= 1;}else{c -= 1;}}cout << endl; }

4.0-1背包問題

/**0-1背包 輸入：一個容量V的背包，若干寶石，價值體積各不同。 輸出：可能裝入寶石的最大價值 分析：這是一種有限制條件的動態規劃問題，因此通常需要一個額外的狀態來刻畫限制條件。1.首先把大問題轉化成小問題，假設s[i]代表加入前個寶石能達到的最大價值。這并沒有體現背包容量的限制。因此使用s[i][j]表示把前i個寶石裝入到剩余體積j的背包中能達到的最大價值。2.由狀態分析狀態轉移方程，思考d[i][j]與d[i-1]的關系。顯然兩種情況，既是裝入和不裝入第i件物品。 狀態：d[i][j]把前i個寶石裝入到剩余體積j的背包里能達到的最大價值 狀態轉移方程：d[i][j]=max(d[i-1][j-vo[i]]+va[i], d[i-1][j]) */ void knapsack() {const int V = 12;vector<int> value = { 10, 9, 6, 1, 4, 9, 20, 6, 20, 4 };vector<int> volume = { 5, 4, 3, 5, 2, 6, 4, 4, 3, 4 };vector<vector<int>> d(value.size()+1);for (auto& e:d){e.resize(V+1);}int j = V;for (int i = 0; i < value.size();++i){for (int j = 0; j < V; ++j){d[i + 1][j + 1] = d[i][j + 1];if (j>=volume[i] && d[i + 1][j + 1] < d[i][j + 1 - volume[i]] + value[i])d[i + 1][j + 1] = d[i][j + 1 - volume[i]] + value[i];}}cout << "max value: " << d[value.size()][V] << endl;cout << "they are: " << endl;//vector<int> table(value.size());j = V;for (int i = value.size()-1; i >= 0; --i){if (d[i + 1][j] > d[i][j]){cout << value[i] << "\t";j -= volume[i];}}cout << endl; }

參考

http://hawstein.com/posts/dp-novice-to-advanced.html

http://blog.csdn.net/zmazon/article/details/8247015

?

轉載于:https://www.cnblogs.com/tpys/p/3891816.html

總結

以上是生活随笔為你收集整理的循序渐进动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。