动态规划实现矩阵连乘策略

矩阵连乘问题是一个经典的动态规划问题。对于给定的$n$个矩阵$A_1,A_2,\dots,A_n$，我们需要将它们相乘，求出最优的计算顺序，使得计算代价最小。

设$A_i$的规模为$p_{i-1}\times p_i$，则其乘法代价为$p_{i-2} \times p_{i-1} \times p_i$。因此，如果我们将前$k$个矩阵分成一组，后$n-k$个矩阵分成一组，则总的代价为：

$$
m_{1,n}=m_{1,k}+m_{k+1,n}+p_{0} \times p_{k} \times p_{n}
$$

其中，$m_{i,j}$表示从第$i$个矩阵到第$j$个矩阵的最小乘法代价。根据上面的公式，我们可以得到递推式：

$$
m_{i,j} = \min_{i\leq k<j}\{m_{i,k}+m_{k+1,j}+p_{i-1} \times p_k \times p_j\}
$$

边界条件为$m_{i,i}=0$，表示只有一个矩阵时，乘法代价为0。

我们可以使用一个二维数组$dp$来进行状态转移。$dp[i][j]$表示从第$i$个矩阵到第$j$个矩阵的最小乘法代价。最后，$dp[1][n]$就是问题的解。

下面是Python代码实现：

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[float('inf')] * (n+1) for _ in range(n+1)]  # 初始化为正无穷
    for i in range(1, n+1):
        dp[i][i] = 0  # 边界条件
    for l in range(2, n+1):  # 子问题规模从小到大
        for i in range(1, n-l+2):
            j = i + l - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
    return dp[1][n]

其中，$p$是一个列表，表示$n+1$个矩阵的规模。例如，$p=[10, 20, 30, 40]$表示有$3$个矩阵，第一个矩阵的规模为$10\times20$，第二个矩阵的规模为$20\times30$，第三个矩阵的规模为$30\times40$。