U519157 矩阵连乘题解

请注意：本题改编自P1753 矩阵链排序问题

U519157 矩阵连乘

1. 把原始问题分解乘除规模变小外与原始问题相同的子问题
2. 若干子问题较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。
3. 将已求解的各个子问题的解，逐步合并为原问题的解。

预备知识：矩阵乘法

矩阵乘法常常指的是一般矩阵乘法。设矩阵$A = (a_{ij})_{m \times n}$和$B = (b_{ij})_{m \times s}$,令$C=(c_{ij})_{m \times s}$。其中$c_{ij} = \displaystyle\sum_{k=1}^na_{ik}b_{kj}(1 \leq i \leq m,1\leq j\leq s)$，那么矩阵$C$称为矩阵$A$与$B$的乘积，记为$C=AB$ 或 $C=A \cdot B$。为方便，称被乘数$A$为左矩阵，乘数$B$为右矩阵。

注意事项：

• 只有左矩阵的列数与右矩阵的行数相同的两个矩阵才能相乘。
• 乘积矩阵第i行第j列处的元素等于左矩阵的第i行与右矩阵的第j列对应元素乘积之和，即$\big( AB\big)_{ij}=\displaystyle\sum_{k=1}^na_{ik}b_{kj}$。
• 乘积矩阵的行数等于左矩阵的行数，列数等于右矩阵的列数。

计算示例： 设$A = \begin{bmatrix}1 & -2 \\ 3 & 0 \\ -4 & 5\end{bmatrix}$,$B = \begin{bmatrix}-7 & 8 \\ 9 & 10\end{bmatrix}$,下面计算$AB$:

$$AB=\begin{bmatrix}1 & -2 \\ 3 & 0 \\ -4 & 5\end{bmatrix}\cdotp\begin{bmatrix}-7 & 8 \\ 9 & 10\end{bmatrix}\\ =\begin{bmatrix}1\times(-7)+(-2)\times9 & 1\times 8+(-2)\times10\\3\times(-7)+0\times9 & 3\times8+0\times10\\(-4)\times(-7)+5\times9 & (-4)\times8+5\times10\end{bmatrix} \\=\begin{bmatrix}-25 & -12 \\ -21 & 25 \\ 73 & 18\end{bmatrix}$$

1. 穷举 在穷举算法的前提下，这道题就是让我们求 “有$n$个数相乘，在括号里只能有两个数的情况下根据乘法分配律加括号，问有多少种加括号的方法” 。答案是第$(n-1)$个卡特兰数(证明在附录)。我们观察数据范围:$1 \leq n \leq 500$，$h(499 )=135,279,399,872,590,875,633,440,787,600,588,225,974,050,054,277,551,695,198,895,332,886,198,913,266,027,124,073,379,621,583,835,020,102,784,087,129,640,413,465,866,971,846,872,212,170,945,893,002,852,611,849,561,394,136,268,144,010,688,770,002,041,910,854,526,708,996,076,636,385,187,472,995,488,366,510,450,708,008,505,615,328,704,888,346,274,576,144,575,877,119,333,388,036,489,421,321,231,840$这么庞大的数，绝对超时，所以不考虑
2. 动态规划

1. 找出最优解的性质（分析最优解的结构），并刻画其结构特征
2. 递归地定义最优值
3. 以自底向上的方式计算出最优值
4. 根据计算最优值时得到的信息，构造最优解（可选）

根据矩阵乘法规则可以得出$m$行$n$列的$A$矩阵乘$n$行$k$列的$B$矩阵的乘法次数为$nmk$，证明略。

int n, p[510], m[510][510], s[510][510];

void MatrixChain(int n) {
	//计算所有长度为 1 的子问题 A[i:i] 的最小计算次数 (递归出口)
	for(int i = 1; i <= n; i++) m[i][i] = 0;						 
	
	//计算长度为 2 ~ n 的子问题 
	for(int r = 2; r <= n; r++) {
		//r控制子问题长度,保证从 2 到 n 的顺序计算计算子问题 
		for(int i = 1; i <= n - r + 1; i++) {
			/* i 控制长度为 r 的子问题的起始矩阵下标 
			   n - r + 1是保证长度为 r 的矩阵链成立的最大下标 */ 
			int j = i + r - 1;		//长度为 r 的矩阵链的最后一个下标
			
			/*尝试不同切割, 找出最优切割 ( i <= k < j, 相当于尝试不同的 k ) 
			
                  /
                  |								0								i = j
           m[i] = | 
                  |  min(i <= k < j){ m[i][k] + m[k+1][j] + P[i-1]P[k]P[j] }	i < j
                  \
			*/
			
			m[i][j] = /*m[i][i] + */m[i + 1][j] + p[i - 1] * p[i] * p[j];	// k = i 的情况
			//实际上 m[i][i]可以省略, 因为值是 0 
			s[i][j] = i;
			//s数组是用来记录最优分割的位置的
			
			//其它 k 取值 ( i + 1 ~ j + 1 ) ——其他切割 
			for(int k = i + 1; k < j; k++) {
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if(t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void print(int i, int j) {
	if(i == j) printf("A%d", i);
	else {
		printf("(");
		print(i, s[i][j]);
		print(s[i][j] + 1, j);
		printf(")");
	}
}

对于$n$个数相乘，且每次括号里只能包含两个数，我们可以通过不同的方式加括号来改变计算的顺序。例如，对于三个数$a$、$b$、$c$，有两种括号化方式：$(ab)c$ 和 $a(bc)$。对于四个数$a$、$b$、$c$、$d$，有五种括号化方式:$((ab)c)d$、$(a(bc))d$、$(ab)(cd)$、$a((bc)d)$、$a(b(cd))$。不难发现，随着n的增加，括号化的方式会迅速增多。这个问题实际上与组合数学中的卡特兰数（Catalan number）有关。对于$n$个数相乘的括号化方式，其数量等于第$(n-1)$个卡特兰数。卡特兰数的通项公式为:$h(n)=\displaystyle\frac{C_{2n}^{n}}{n + 1}$。其中，$C_{2n}^{n}$是二项式系数，表示从$2n$个元素中选取$n$个元素的组合数。但是，对于括号化乘法的问题，更直接的递推公式是：$h(n)=\displaystyle\sum_{k=1}^{n-1}h(k)h(n-k)$其中，$h(1) = 1$。这个递推公式的意思是，对于$n$个数的括号化，可以选择第一个操作是前$k$个数和后$(n-k)$个数的乘积的乘积，其中$k$从$1$到$n-1$。例如，对于$n=3$：$h(3) = h(1)h(2) +h(2)h(1) = 11 + 11 = 2$对于$n=4$：$h(4) = h(1)h(3) + h(2)h(2) + h(3)h(1) = 12 + 11 + 21 = 5$这与我们之前列举的四种情况相符。因此，$n$个数相乘，每次括号里只能包含两个数的加括号方法数是第$(n-1)$个卡特兰数。所以，答案是第$(n-1)$个卡特兰数。