c语言动态规划求矩阵连乘

矩阵连乘问题可以通过动态规划求解，具体思路如下：

设矩阵链为 A1, A2, ..., An，其中 Ai 的维数为 pi-1 × pi，i=1,2,...,n+1

设m[i][j]表示矩阵链AiAi+1···Aj的最小乘次数，则有以下状态转移方程：

m[i][j] = 0, if i = j
m[i][j] = min{m[i][k] + m[k+1][j] + pi-1 × pk × pj}, i ≤ k < j

其中，i和j分别表示矩阵链的起点和终点，k是在链中加入一个括号后的分割点，pi-1 × pk × pj表示将两个矩阵相乘的代价。

最终，m[1][n]即为矩阵链的最小乘次数。

下面是C语言代码实现：

#include <stdio.h>
#include <limits.h>

int MatrixChainOrder(int p[], int n)
{
    int m[n][n];
    int i, j, k, L, q;

    for (i = 1; i <= n; i++)
        m[i][i] = 0;

    for (L = 2; L <= n; L++)
    {
        for (i = 1; i <= n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            for (k = i; k <= j-1; k++)
            {
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }

    return m[1][n];
}

int main()
{
    int arr[] = {1, 2, 3, 4, 3};
    int size = sizeof(arr)/sizeof(arr[0]);

    printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, size-1));

    return 0;
}

其中，p数组存储矩阵链的维数信息。