题目：

矩阵的乘法定义如下：设A是m×p的矩阵，B是p×n的矩阵，则A与B的乘积为m×n的矩阵，记作C=AB，其中，矩阵C中的第i行第j列元素 $c_{ij}$ 可以表示为：

$$c_{ij}=\sum _{k=1}^p{a}_{ik}\times b_{kj}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{ip}{b}_{pj}$$

当多个矩阵相乘时，采用不同的计算顺序所需的乘法次数不相同。例如，A是50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵，计算ABC有两种方式：(AB)C和A(BC)，前一种需要15000次乘法计算，后一种则只需3500次。

设 $A_1,A_2,...,A_n$ 为矩阵序列，$A_i$ 是阶为 $P_{i-1}\times P_i$ 的矩阵 (1≤i≤n)。试确定矩阵的乘法顺序，使得计算 $A_1{A}_2...A_n$ 过程中元素相乘的总次数最少。

输入格式:
每个输入文件为一个测试用例，每个测试用例的第一行给出一个正整数n(1≤n≤500)，表示一共有n个矩阵 $A_1,A_2,...,A_n$，第二行给出n+1个整数 $P_0,P_1...P_n$，以空格分隔，其中1≤$P_i$≤100(0≤i≤n)，第i个矩阵 $A_i$ 是阶为 $P_{i-1}\times P_i$ 的矩阵。

** 输出格式:**
获得上述矩阵的乘积，所需的最少乘法次数。

输入样例:
在这里给出一组输入。例如：

5
30 35 15 5 10 20

输出样例：
在这里给出相应的输出。例如：

11875

---

解题思路（递归、迭代通用）

多个矩阵相乘，最后一定可以写成两个矩阵相乘的形式：

$A_i\ast A_2\ast ...\ast A_j$ = $(A_i\ast ...\ast A_k)\ast (A_{k+1}\ast ...\ast A_j)$， $k$ 为分割的位置

$k$取值$[i,j-1]$

我们以$m(i,j)$表示从矩阵i乘到矩阵j的最少乘法次数。通过观察从 $i$ 到 $j-1$ 的分割方案，从中选择乘法次数最小的，就可以得到$m(i,j)$。

也就是说，问题与它的子问题之间存在这样的依赖关系：

$m(i,j)=mi{n}_{k=i}^{j-1}(m(i,k)+m(k+1,j)+p_{i-1}\ast p_k\ast p_j)$

由此，便可以得出$m(i,j)$的递归定义：

①当$i$ = $j$时， $m(i,j)$ = 0;（即只有一个矩阵，乘法次数当然为0）
②当$i$ < $j$时，$m(i,j)=mi{n}_{k=i}^{j-1}(m(i,k)+m(k+1,j)+p_{i-1}\ast p_k\ast p_j)$

①可以理解为初始值，②是状态转移方程（或者称为原问题和子问题之间依赖关系）

有了初始值和状态转移方程，这题已经十拿九稳了。

---

递归解法（最简单，从代码将递推公式表达出来就行）

递推解法是自顶向下的（后面的迭代解法顺序相反）

//矩阵乘法最少次数_递归解法 
#include<bits/stdc++.h>
using namespace std;
#define size 510 

int p[size];
int m[size][size]; //m[i][j]-从矩阵i乘到矩阵j的最少乘法次数

int recMatrixMul(int i, int j){
	if(i == j) return 0; //公式①：初始值
	
	m[i][j] = INT_MAX; //公式②：依赖关系 
	for(int k=i; k<j; k++){
		int temp = recMatrixMul(i, k) + recMatrixMul(k+1, j) + p[i-1]*p[k]*p[j];
		if(temp < m[i][j]){
			m[i][j] = temp;
		}
	}
	
	return m[i][j];
} 

int main(){
	int n;
	cin>>n;
	
	for(int i=0; i<=n; i++){
		cin>>p[i];
	}
	
	recMatrixMul(1, n);
	
	cout<<m[1][n];
}

---

递归+备忘录

由于子问题会被重复计算，大大增加了时间复杂度（为指数级）。所以建立一个备忘录保存之前子问题的结果。其实我们之前用的$m[i][j]$就保存了子问题的解。

//矩阵乘法最少次数_递归+备忘录 
#include<bits/stdc++.h>
using namespace std;
#define size 510 

int p[size];
int m[size][size]; //m[i][j]-从矩阵i乘到矩阵j的最少乘法次数

int recMatrixMul(int i, int j){
	if(i == j) return 0;
	if(m[i][j]>0) return m[i][j]; //每次先检查备忘录，如果该子问题已经求解过，就直接把结果拿来用
	
	m[i][j] = INT_MAX;
	for(int k=i; k<j; k++){
		int temp = recMatrixMul(i, k) + recMatrixMul(k+1, j) + p[i-1]*p[k]*p[j];
		if(temp < m[i][j]){
			m[i][j] = temp;
		}
	}
	
	return m[i][j];
} 

int main(){
	int n;
	cin>>n;
	
	for(int i=0; i<=n; i++){
		cin>>p[i];
	}
	
	recMatrixMul(1, n);
	
	cout<<m[1][n];
}

---

迭代解法

迭代解法是自底向上的，需要考虑计算的顺序，确保在求解当前问题时，它的子问题已经有解了，否则就会出错。

计算顺序，需要再次观察$m(i,j)$的递归定义：

①当$i$ = $j$时， $m(i,j)$ = 0;（即只有一个矩阵，乘法次数当然为0）
②当$i$ < $j$时，$m(i,j)=mi{n}_{k=i}^{j-1}(m(i,k)+m(k+1,j)+p_{i-1}\ast p_k\ast p_j)$

假如我们现在求解的问题是$m(i,j)$，根据递推公式我们必须知道 $m(i,k)$ 和 $m(k+1,j)$，$i,j,k$关系很简单：

$(A_i\ast ...\ast A_k)\ast (A_{k+1}\ast ...\ast A_j)$，显然$i<=k<j$

也就是说，我们必须知道在二维数组 $m[i][j]$ 中，与 $(i,j)$ 在 同一列下面的元素值 和 同一行左边的元素值。因此求解顺序为从下往上，再从左往右。（下图为求$m[2][4]$需要知道的子问题）

	j=1	j=2	j=3	j=4	…	j=n
i=1	0
i=2		0	m[2][3]	m[2][4]
i=3			0	m[3][4]
i=4				0
…					…
i=n						0

//动态规划，迭代（填表顺序，从下往上，从左至右），矩阵乘法最少次数
#include<bits/stdc++.h>
using namespace std;
#define size 510 

int p[size];
int m[size][size]; //m[i][j]-从矩阵i乘到矩阵j的最少乘法次数

int MatrixMul(int i, int n){
	for(int i=1; i<=n; i++){ //初始化 
		m[i][i] = 0;
	}
	
	for(int i=n; i>=1; i--){ //填表：从下往上
		for(int j=i+1; j<=n; j++){//填表：从左往右
			m[i][j] = INT_MAX;
			for(int k=i; k<j; k++){
				int temp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if(temp < m[i][j]){
					m[i][j] = temp;
				}		
			}
		}
	}
	
	return m[i][n];
} 

int main(){
	int n;
	cin>>n;
	
	for(int i=0; i<=n; i++){
		cin>>p[i];
	}
	
	MatrixMul(1, n);
	
	cout<<m[1][n];
}

---

小结：

动态规划的要点在于 找到状态转移方程（也就是当前问题与子问题之间存在怎样的关系）。

找到状态转移方程后，基本上照着公式写就OK了（另外还需考虑一些细节问题：初始化（可以马上解决的问题）、填表的顺序（通过观察状态转移方程））。

对于迭代的动态规划，尤其需要注意填表的顺序问题。