《算法导论》15.3 动态规划原理（含有矩阵链问题的改良&&C++代码）

最优子结构

1、用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如前文所述，如果一个
问题的最优解包含其子问题的最优解我们就称此问题具有最优子结构性质。
2、对于不同问题领域，最优子结构的不同体现在两个方面:
（1）原问题的最优解中涉及多少个子问题
（2）在确定最优解使用哪些子问题时，我们需要考察多少种选择。
3、在动态规划方法中，我们通常自底向上地使用最优子结构。也就是说，首先求得子问题的最
优解，然后求原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价再加上由此次选择直接产生的代价。
例如，对于钢条切割问题，我们首先求解子问题，确定长度为i=0,1,… n-1的钢条的最优切割方案，然后利用公式(15.2)确定哪个子问题的解构成长度为n的钢条的最优切割方案。此次选择本身所产生的代价就是公式(15.2)中的p_i。

重叠子问题

1、递归算法一直都在反复求相同的子问题，那么就说最优化问题具有重叠子问题。
2、下图就可以看到查表操作的优势在哪里，不用反复求同一个子问题了。

重构最优解（优化矩阵链乘法）

MEMORIZED-MATRIX-CHAIN(p)
n = p.length - 1
let m[1...n,1...n] be a new table
for i = 1 to n
	for j = i to n
		m[i,j] = ∞
return LOOKUP-CHAIN(m, p, 1, n)
1
2
3
4
5
6
7

LOOKUP-CHAIN(m,p,i,j)
if m[i,j] < ∞
	return m[i,j]
if i==j
	m[i,j] = 0
else for k = i to j-1
	q = LOOKUP-CHAIN(m, p, i, k) + LOOKUP-CHAIN(m, p, k+1, j) + pi-1 pk pj
	if q < m[i,j]
		m[i,j] = q
return m[i,j]
1
2
3
4
5
6
7
8
9
10

C++代码

#include 
#include 
using namespace std;
int LookUpChain(int(*m)[10], int(*s)[10], vector<int>& v, int i, int j);
int MemorizedMatrixChain(vector<int>&v, int(*m)[10], int(*s)[10])
{
	int n = v.size() - 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			m[i][j] = INT_MAX;
		}
	}
	return LookUpChain(m, s,v, 1, n);
}
int LookUpChain(int(*m)[10] , int(*s)[10],vector<int>& v, int i, int j)
{
	int q;
	if (m[i][j] < INT_MAX) {
		return m[i][j];
	}
	if (i == j) {
		m[i][j] = 0;
	}
	else for (int k = i; k <= j - 1; k++) {
		q = LookUpChain(m, s,v, i, k)+LookUpChain(m,s,v,k+1,j)+v[i-1]*v[k]*v[j];
		if (q < m[i][j]) {
			m[i][j] = q;
			s[i][j] = k;
		}
	}
	return m[i][j];
}
void PrintOptimalParens(int(*s)[10], int i, int j)
{
	if (i == j)
	{
		cout << 'A' << i;
	}
	else {
		cout << "(";
		PrintOptimalParens(s, i, s[i][j]);
		PrintOptimalParens(s, s[i][j] + 1, j);
		cout << ")";
	}
}
int main()
{
	vector<int>v1;
	int n;
	cout << "Please enter the number you want!" << endl;
	cin >> n;
	cout << "Please enter the numbers!" << endl;
	int number;
	for (int i = 0; i < n; i++) {
		cin >> number;
		v1.push_back(number);
	}
	int m[10][10], s[10][10];
	int result = MemorizedMatrixChain(v1,m,s);
	cout << "result:" << result<<endl;
	PrintOptimalParens(s, 1, 6);
	cout << endl;
	return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64