作业8：动态规划用于矩阵链最少乘法问题

1.问题

设{A_1,A_2,...,A_n}为n个矩阵序列，其中{A_i=P_{i-1}*P_i}阶矩阵，矩阵链的输入用向量P=<{P_1,P_2,...,P_n}>

给定向量P，确定一种方案使矩阵链的乘法次数最少。

2.解析

我们定义a_{i,j}为矩阵链相乘问题A_i至A_j之间的子问题，并称dp_{i,j}为实现该子问题所需的最小标量乘法次数；s_{i,j}则用于记录获得这一最小值时所采用的最佳分割位置。 因为

所以我们可以推导出动态规划方程：当i等于j时，则dp[i][j]的值为零；而当i小于j时，则有公式表示为：dp[i][j] = \min\left(dp[i][k] + dp[k+1][j] + P_{i-1} \cdot P_j \cdot P_k\right)其中i \leq k < j。为了验证上述公式是否符合优化策略的要求，请证明以下等式成立：$$\forall i \leq j, \quad dp[i][j] = \min\left(dp[i][k] + dp[k+1][j] +