矩阵连乘问题：动态规划、直接递归、备忘录算法实现

一、实验目的

了解动态规划法思想； 掌握动态规划算法步骤； 学会使用动态规划算法、直接递归算法、备忘录算法实现矩阵连乘。

二、实验内容

1. 问题描述

给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 请使用动态规划算法、直接递归算法、备忘录算法三种方法实现矩阵连乘。

输入：矩阵个数， 如：3

       依次输入矩阵的行数和最后一个矩阵的列数， 如：10 5 15 10 

输出：最小计算量的值 ，构造最优解

2. 要求：

（1） 写出问题的分析过程 （2） 写出程序代码

内容：问题分析过程：

1. 首先，我们需要确定如何表示矩阵连乘的计算次序。我们可以使用一个二维数组dp[i][j]来表示从矩阵Ai到Aj的最少数乘次数。其中，i<=j，当i=j时，dp[i][j]=0。

2. 接下来，我们需要确定动态规划的递推方程。对于任意的i和j，我们可以将矩阵连乘分为两部分：Ai到Ak和Ak+1到Aj，其中i<=k<j。则dp[i][j]的递推方程可以表示为：

   dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])

   其中p[i-1]表示矩阵Ai-1的行数，p[k]表示矩阵Ak的行数，p[j]表示矩阵Aj的列数。

3. 最后，我们需要确定动态规划的计算顺序。由于dp[i][j]依赖于dp[i][k]和dp[k+1][j]，所以我们需要按照矩阵连乘的长度从小到大进行计算。

程序代码：

1. 动态规划算法实现矩阵连乘

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for l in range(2, n+1):
        for i in range(n-l+1):
            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]*p[k+1]*p[j+1])
    return dp[0][n-1]

2. 直接递归算法实现矩阵连乘

def matrix_chain_order_recursive(p, i, j):
    if i == j:
        return 0
    min_cost = float('inf')
    for k in range(i, j):
        cost = matrix_chain_order_recursive(p, i, k) + matrix_chain_order_recursive(p, k+1, j) + p[i-1]*p[k]*p[j]
        if cost < min_cost:
            min_cost = cost
    return min_cost

3. 备忘录算法实现矩阵连乘

def matrix_chain_order_memo(p):
    n = len(p) - 1
    memo = [[float('inf')] * n for _ in range(n)]
    return matrix_chain_order_memo_helper(p, 0, n-1, memo)

def matrix_chain_order_memo_helper(p, i, j, memo):
    if i == j:
        return 0
    if memo[i][j] != float('inf'):
        return memo[i][j]
    min_cost = float('inf')
    for k in range(i, j):
        cost = matrix_chain_order_memo_helper(p, i, k, memo) + matrix_chain_order_memo_helper(p, k+1, j, memo) + p[i-1]*p[k]*p[j]
        if cost < min_cost:
            min_cost = cost
    memo[i][j] = min_cost
    return min_cost