第十四章我想放在后面再看，先擱下。希望大家總結的一些文章也能向我推薦下，大家互相學習。

首先，還是建議看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

其次，阿門，感謝老天送給了我們這么一本圣經，看了這一章，再次感受到了《算法導論》分析問題的精辟，強悍的魅力。Orz, Orz,各種Orz。

這一章講的是動態規劃，學算法的朋友，尤其是搞ACM的，對這個策略一定非常熟悉，所以這個算法網上的分析講解教程也是鋪天蓋地，大家可以多搜幾篇學習學習。

動態規劃(Dynamic Programming，簡稱DP)是通過組合子問題的解來解決問題的。

注意這里的programming不是指編程，而是指一種規劃。

因為DP用的太廣泛了，并且書上也花了很大的篇幅來講這一章，所以我也準備把這一章分幾篇來總結，并且我不按照書上的順序來總結，也不會全部用書上的例子。

這一章首先給出一些基礎的概念，然后給出一個最基礎入門的DP問題，三角形求值問題。

DP適用于子問題不是獨立的情況，這樣如果用分治法，也會作許多重復的工作，而DP只對子問題求解一次，將其結果保存在一張表中，從而避免了每次遇到各個子問題時重新計算的情況。

比較分治法于動態規劃的區別：

分治法：將問題劃分為一些獨立的子問題，遞歸的求解各子問題，然后合并子問題的解而得到原問題的解。

eg.

MERGE-SORT(A, p, r)
1 if p < r
2   then q ← |(p + r)/2|
3        MERGE-SORT(A, p, q)
4        MERGE-SORT(A, q + 1, r)
5        MERGE(A, p, q, r)

動態規劃：適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題，鑒于會重復的求解各子問題，DP對每個問

題只求解一遍，將其保存在一張表中，從而避免重復計算。

DP算法的設計可以分為四個步驟：

①.描述最優解的結構。

②.遞歸定義最優解的值。

③.按自底而上的方式計算最優解的值。

④.由計算出的結果創造一個最優解。

下面來看看三角形求值這個問題：

將一個由N行數字組成的三角形，如圖所以，設計一個算法，計算出三角形的由頂至底的一條路徑，使該路徑經過的數字總和最大。

這是在我見過的DP題目中，算是最簡單的了，我相信就算沒有學過DP的也會。

將上圖轉化一下：

假設上圖用map[][]數組保存。

令f[i][j]表示從頂點(1, 1)到頂點(i, j)的最大值。

則可以得到狀態轉移方程：

f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]

此題既適合自頂而下的方法做，也適合自底而上的方法，

當用自頂而下的方法做時，最后要在在最后一列數中找出最大值，

而用自底而上的方法做時，f[1][1]即為最大值。

所以我們將圖2根據狀態轉移方程可以得到圖3：

最大值是30.

很簡單的DP題，代碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
Description: 動態規劃之三角形求值問題
*/
#include <iostream>
using namespace std;
 
int map[6][6] = 
{
	{0, 0, 0, 0, 0, 0},
	{0, 7, 0, 0, 0, 0},
	{0, 3, 8, 0, 0, 0},
	{0, 8, 1, 0, 0, 0},
	{0, 2, 7, 4, 4, 0},
	{0, 4, 5, 2, 6, 5}
};
 
int f[6][6];
 
int _max(int a, int b)
{
	if(a >= b)
		return a;
	return b;
}
 
int main()
{
	memset(f, 0, sizeof(f));
	for(int i=0; i<6; ++i)
		f[5][i] = map[5][i];
	for(int i=4; i>=1; --i)
		for(int j=1; j<=i; ++j)
			f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
	for(int i=1; i<=5; ++i)
	{
		for(int j=1; j<=5; ++j)
		{
			cout.width(2);
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	cout << f[1][1] << endl;
}

結果如圖：

下一篇會將裝配線的調度。

在我獨立博客上的原文：http://www.wutianqi.com/?p=2484

歡迎大家互相學習，互相進步！