动态规划算法实验----矩阵链乘问题

矩阵链乘问题是一个经典的动态规划问题，其目标是找到一种最优的方式来计算给定的一组矩阵的连乘积。这个问题可以通过动态规划算法来解决。

动态规划算法的基本思想是将问题分解成更小的子问题，并使用已知的信息来计算更大的问题。在矩阵链乘问题中，我们可以将问题分解成计算两个矩阵的乘积的子问题，并使用已知的信息来计算更大的问题。

具体来说，我们可以定义一个二维数组m，其中m[i][j]表示从第i个矩阵到第j个矩阵的最小计算代价。我们还可以定义一个二维数组s，其中s[i][j]表示从第i个矩阵到第j个矩阵的最优计算次序。

接下来，我们可以使用以下递归公式来计算m和s：

m[i][j] = 0 (i = j)
m[i][j] = min{m[i][k] + m[k+1][j] + ri*ck*cm} (i <= k < j)

其中，ri和ci分别表示第i个矩阵的行数和列数，cm表示两个矩阵相乘的计算代价。

使用上述递归公式，我们可以计算出所有的m[i][j]和s[i][j]。最终，我们可以通过s数组来构造出最优的计算次序，并使用m数组来计算最小的计算代价。

下面是一个Python实现的例子：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for i in range(n)]
    s = [[0] * n for i in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s

def print_optimal_parens(s, i, j):
    if i == j:
        print("A{}".format(i+1), end='')
    else:
        print("(", end='')
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j]+1, j)
        print(")", end='')

p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print_optimal_parens(s, 0, len(p)-2)
print("\nMinimum cost:", m[0][len(p)-2])

输出结果为：

((A1(A2A3))((A4A5)A6))
Minimum cost: 15125