动态规划简介

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

矩阵连乘问题的定义

输入：n个矩阵A1,A2,…,An，其中Ai的维数为pi-1×pi
Ai 和Ai+1是可乘的

输出：连乘积A1A2A3…An

优化目标：最小计算代价（最优的计算次序）

矩阵乘法的代价：乘法次数
若A 是p ×q 矩阵，B 是q ×r 矩阵，则A ×B 的代价是pqr
因为矩阵乘法满足结合律，因此矩阵连乘可以由不同的计算次序，这种计算次序可以用加括号来表示。

三个矩阵A1: 10×100, A2: 100×5，A3: 5×50
(A1A2)A3
代价：10×100×5＋10×5×50＝7500
A1(A2A3)
代价：100×5×50＋10×100×50＝75000

可见不同的计算次序会导致不同的计算代价，我们要做的就是让这个代价最小。

我们自然可以用穷举法计算每次不同的结合次序带来的不同代价，然后取最小值，但是这样我们得到的复杂度将达到

分析最优解结构

将矩阵连乘积AiAi+1…Aj，记为A[i:j]

设AiAi+1…Aj的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开得到：(Ai… Ak) (Ak+1 …Aj)

总的计算量就是：A[i:k]的计算量＋A[k+1: j]的计算量+A[i:k]和A[k+1:j]相乘的计算量

建立的递归关系就是

计算A[i:j]所需的最小乘法次数为m（i，j）

其中Ai是Pi-1 x Pi的矩阵

接下来我们借助填表过程理解递归的过程，现在给出下列矩阵：

填表过程是按对角线填写的，只利用到了二维数组的右上角一部分。

根据地推公式，我们可以知道，在i=j时m=0，所以先构造出最长的对角线部分的数据，如下图：

现在我们继续构造，
m（1,2）=min{m[1][1]+m[2][2]+p0p1p2}={0+0+303515}=15750

m(2,3) = min(m[2][2]+m[3][3]+p1p2p3=0+0+35155）=2625

同理，后面不再一一列举；

再多说一点，有时我们会遇到有多个划分，我们取最小值就可以了，

例如：m（1,4）=min{m[1][2]+m[3][4]+p0p2p4 或者是 m[1][1]+m[2][4]+p0p1p4或者是m[1][3]+m[4][4]+p0p3p4}，其中的值已经在前面求出来了，这也是动态规划要记录所有值的原因。

结果图如下：读者可以自行计算验证。

那么，我们最后如何得知是哪个地方要加括号呢？
根据最后的公式。

例如，假设最后的m[1:6]=m[1,1]+m[2][6]+p0p2p6（笔者构造的，跟上面的例子没关系），那么我们就知道是（A1(A2A3A4A5A6)）,再看m[2:6],根据公式找退出括号位置，一直推到最后即可。

我们不难发现，加括号的位置其实就是k 的对应序号的矩阵，在写算法时我们就可以用另外的数组记录下对应位置的k值。在最后输出时把这个数组按逻辑输出。

最终这个算法的复杂度

代码如下：(摘录自：大佬的博客中的代码)

#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)//初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)//r个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
		{
			j = i + r - 1;
			m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
				if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}
void print(int i, int j)
{
	if (i == j)
	{
		cout << "A[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);//递归1到s[1][j]
	cout << ")";
}
int main()
{
	int n;//n个矩阵
	cin >> n;
	int i, j;
	for (i = 0; i <= n; i++)
	{
		cin >> A[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}

动态规划算法的基本要素

适用条件

1.优化子结构
2.重叠子问题

设计步骤

1.找出最优解性质，刻画结构特征

2.递归地定义最优解

3.自底向上的方式计算最优解

4.根据计算最优解时得到的信息，构造最优解