c语言：1．矩阵连乘问题 【问题描述】 给定 n 个矩阵{A1,A2,…,An}，其中 Ai 与 Ai+1 是可乘的，i=1,2…,n-1， 如何确定矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的乘法次 数最少。 例，有四个矩阵 A, B, C, D，它们的维数分别是： A=50× 10， B=10× 40, C=40× 30, D=30× 5，连乘积 ABCD 共有五种完全加括号的方式： 矩阵连乘问题的乘法次数 (A((BC)D)) 16000 (A(B(CD))) 10500 ((AB)(CD)) 36000 (((AB)C)D) 87500 ((A(BC))D) 34500 【算法设计】给出算法设计思想，并用动态规划算法实现

算法设计思想：

对于矩阵连乘问题，可以使用动态规划算法来解决。具体来说，我们可以定义一个二维数组dp，其中dp[i][j]表示从矩阵Ai乘到矩阵Aj所需的最少乘法次数。那么，dp[i][j]可以通过枚举其中一个断点k来计算得到，即：

dp[i][j] = min{dp[i][k] + dp[k+1][j] + mi[i]*mi[k+1]*mi[j+1]} (i ≤ k < j)

其中mi[i]表示矩阵Ai的行数，也是矩阵Ai与Ai-1相乘后的行数，矩阵Ai的列数也是矩阵Ai-1与Ai相乘后的列数。

动态规划转移方程的含义是，将矩阵序列分成两部分，分别计算左边部分和右边部分的最少乘法次数，再加上这两部分相乘的乘法次数，得到总的最少乘法次数。

最终，矩阵连乘积的最少乘法次数为dp[1][n]。

代码实现：

#include <stdio.h>

#define MAXN 100

int mi[MAXN + 1]; // 矩阵维数
int dp[MAXN + 1][MAXN + 1]; // dp数组

int main()
{
    int n; // 矩阵个数
    scanf("%d", &n);
    for (int i = 1; i <= n + 1; i++)
        scanf("%d", &mi[i]);

    // 初始化
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;

    // 动态规划转移
    for (int len = 2; len <= n; len++) // 枚举区间长度
    {
        for (int i = 1; i <= n - len + 1; i++) // 枚举区间起点
        {
            int j = i + len - 1; // 区间终点
            dp[i][j] = 0x3f3f3f3f; // 初始化为正无穷

            for (int k = i; k < j; k++) // 枚举断点
            {
                int cnt = dp[i][k] + dp[k+1][j] + mi[i]*mi[k+1]*mi[j+1];
                if (cnt < dp[i][j])
                    dp[i][j] = cnt;
            }
        }
    }

    printf("%d\n", dp[1][n]);

    return 0;
}

上述代码中，0x3f3f3f3f表示正无穷，因为最少乘法次数不可能超过矩阵个数的平方，而0x3f3f3f3f是一个比较大的数，可以作为正无穷使用。