下面以一道經典的動態規劃題目說明動態規劃算法的思想。
先看題目：如下圖（圖片來自百度圖片）是一個數塔，從頂部出發在每一個節點可以選擇向左或者向右走，一直走到底層，要求找出一條路徑，使得路徑上的數字之和最大.
思路分析： 這道題目如果使用貪婪算法不能保證找到真正的最大和。 在用動態規劃考慮數塔問題時可以自頂向下的分析，自底向上的計算。 從頂點出發時到底向左走還是向右走應取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經求出才能決策。這樣一層一層推下去，直到倒數第二層時就非常明了。 所以第一步對第五層的8個數據，做如下四次決策： 如果經過第四層2，則在第五層的19和7中肯定是19； 如果經過第四層18，則在第五層的7和10中肯定是10； 如果經過第四層9，則在第五層的10和4中肯定是10； 如果經過第四層5，則在第五層的4和16中肯定是16； 經過一次決策，問題降了一階。5層數塔問題轉換成4層數塔問題，如此循環決策…… 最后得到1階的數塔問題。
算法實現：首先利用一個二維數組data存儲數塔的原始數據（其實我們只使用數組data一半的空間，一個下三角矩陣），然后利用一個中間數組dp存儲每一次決策過程中的結果（也是一個下三角矩陣）。 初始化dp，將data的最后一層拷貝到dp中。dp[n][j] = data[n][j] (j = 1, 2, …, n) 其中，n為數塔的層數。 在動態規劃過程匯總，我們有dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]，最后的結果保存在dp[0][0]中。 對于上面的數塔，我們的data數組如下：
| 9 | ||||
| 12 | 15 | |||
| 10 | 6 | 8 | ||
| 2 | 18 | 9 | 5 | |
| 19 | 7 | 10 | 4 | 16 |
而我們的dp數組如下：
| 59 | ||||
| 50 | 49 | |||
| 38 | 34 | 29 | ||
| 21 | 28 | 19 | 21 | |
| 19 | 7 | 10 | 4 | 16 |
下面是C++代碼的實現（Visual Studio2013通過）：
#include <iostream>#include <algorithm>using namespace std;/************************************************************************//* 數塔問題 *//************************************************************************/const int N = 50;//為了算法寫起來簡單，這里定義一個足夠大的數用來存儲數據(為了避免運算過程中動態申請空間，這樣的話算法看起來比較麻煩，這里只是為了算法看起來簡單)int data[N][N];//存儲數塔原始數據int dp[N][N];//存儲動態規劃過程中的數據int n;//塔的層數/*動態規劃實現數塔求解*/void tower_walk(){ // dp初始化 for (int i = 0; i < n; ++i) { dp[n - 1][i] = data[n - 1][i]; } int temp_max; for (int i = n - 1; i >= 0; --i) { for (int j = 0; j <= i; ++j) { // 使用遞推公式計算dp的值 temp_max = max(dp[i + 1][j], dp[i + 1][j + 1]); dp[i][j] = temp_max + data[i][j]; } }}/*打印最終結果*/void PRint_result(){ cout << "最大路徑和：" << dp[0][0] << '/n'; int node_value; // 首先輸出塔頂元素 cout << "最大路徑：" << data[0][0]; int j = 0; for (int i = 1; i < n; ++i) { node_value = dp[i - 1][j] - data[i - 1][j]; /* 如果node_value == dp[i][j]則說明下一步應該是data[i][j]；如果node_value == dp[i][j + 1]則說明下一步應該是data[i][j + 1]*/ if (node_value == dp[i][j + 1]) ++j; cout << "->" << data[i][j]; } cout << endl;}int main(){ cout << "輸入塔的層數："; cin >> n; cout << "輸入塔的節點數據(第i層有i個節點)：/n"; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { cin >> data[i][j]; } } tower_walk(); print_result();}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667運行結果： 
上面的算法是按照最原始的思路進行書寫的，其實還可以進行優化，這里不做詳細說明。
下面官方的敘述下什么是動態規劃： 動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。（摘自百度百科） 動態規劃處理的對象是針對多階段決策問題。多階段決策問題是指這樣的一類特殊的活動過程：問題可以分解成若干個相互聯系的階段，在每一個階段都要做出決策，形成一個決策序列，該決策序列也稱為一個策略。每次決策依賴于當前狀態，又隨即引起狀態的轉移，決策序列（策略）都是在變化的狀態中產生出來的，故有“動態”的含義。所以這種多階段最優化決策解決問題過程稱為動態規劃。 對于每一個決策序列，可以在滿足問題的約束條件下用一個數值函數（即目標函數）來衡量該策略的優劣。多階段決策問題的最優化目標是獲取導致問題最優值得最優決策序列，即得到最優解。（摘自《算法設計方法與優化》滕國文等編著）
個人感覺動態規劃算法的解決重要的是首先必須有能力將實際問題識別為動態規劃問題，然后是找出優化過程中的遞推關系式，這樣就比較容易了。
新聞熱點
疑難解答
