算法题05：动态规划：求矩阵链乘的最优次序、两字符串的最长公共子串

一、用动态规划方法寻找矩阵链$A_1\times A_2 \times A_3 \times A_4$A1​×A2​×A3​×A4​的最佳乘法结合顺序使得调用的标量乘法次数最小 ，写出计算过程。
$\begin{array}{|c|c|c|c|c|} \hline & A_1 & A_2 & A_3 & A_4 \\ \hline 矩阵大小 & 3\times 5 & 5\times 10 & 10 \times2 & 2\times 4 \\ \hline \end{array}$矩阵大小​A1​3×5​A2​5×10​A3​10×2​A4​2×4​​

解：

用$m[i,j]$m[i,j]表示设计算$A[i:j]$A[i:j]所需最少数乘次数,有递归表示为

​ $m[i, j]=\left\{\begin{array}{cc}0 & i=j \\ \min _{i \leq k<j}\left\{m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}\right\} & i<j\end{array}\right.$m[i,j]={0mini≤k<j​{m[i,k]+m[k+1,j]+pi−1​pk​pj​}​i=ji<j​

	1	2	3	4
1	0	A1A2	min{ A1(A2A3)，(A1A2)A3 }	min{ A1(A2A3A4) (A1A2)(A3A4) (A1A2A3)A4 }
2		0	A2A3	min{ A2(A3A4)，(A2A3)A4 }
3			0	A3A4
4				0

$m[1,2] = A_1 A_2 = 3*5*10 = 150$m[1,2]=A1​A2​=3∗5∗10=150 结果矩阵规模：3*10

$m[2,3] = A_2 A_3 = 5*10*2 = 100$m[2,3]=A2​A3​=5∗10∗2=100 5*2

$m[3,4] = A_3 A_4 = 10*2*4 = 80$m[3,4]=A3​A4​=10∗2∗4=80 10*4

$m[1,3] = min\{A_1(A_2~A~3~)，(A_1 A_2~)A~_3~\}$m[1,3]=min{A1​(A2​ A 3 )，(A1​A2​ )A 3​ }
A₁(A₂A₃) = $m[2,3]$m[2,3] + 3*5*2 = 130 结果矩阵规模：3*2

​ (A₁A₂)A₃ = $m[1,2]$m[1,2] + 3 * 10 *2 = 210 3*2
得$m[1,3]$m[1,3] = $A_1(A_2~A~3~)$A1​(A2​ A 3 ) = 130 3*2

同理有：
$m[2,3] =(A~_2~ A~_3~)A~_4~ = 140$m[2,3]=(A 2​ A 3​ )A 4​ =140 5*4

$m[1,4] = min\{ A_1(A_2A_3A_4)，(A_1A_2)(A_3A_4)，(A_1A_2A_3)A_4 \}$m[1,4]=min{A1​(A2​A3​A4​)，(A1​A2​)(A3​A4​)，(A1​A2​A3​)A4​}
$A_1(A_2A_3A_4) = m[2,4] + 3*5*4 = 200$A1​(A2​A3​A4​)=m[2,4]+3∗5∗4=200
$(A_1A_2)(A_3A_4) = m[1,2]+m[3,4]+3*10*4 = 350$(A1​A2​)(A3​A4​)=m[1,2]+m[3,4]+3∗10∗4=350
$(A_1A_2A_3)A_4 = m[1,3] + 3*2*4 = 154$(A1​A2​A3​)A4​=m[1,3]+3∗2∗4=154

得$m[1,4] = 154$m[1,4]=154

所以最小乘法次数为$m[1,4] = 154$m[1,4]=154 次序为$(A_1(A_2A_3))A_4$(A1​(A2​A3​))A4​ .

二、用动态规划方法计算字符串 $“ABDBDCB”$“ABDBDCB”和字符串 $“BDBCABA”$“BDBCABA” 的最长公共子串。写出计算过程。

求公共子串方法

​ 把两个字符串分别以行和列组成一个二维矩阵。比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。

通过查找出值为1的最长对角线就能找到最长公共子串。

可以得到最长公共子串为$BDB$BDB.