c++用动态规划实现矩阵连乘输出最优断点数

矩阵连乘问题是一个经典的动态规划问题，其最优解可以通过建立一个二维数组来求解。具体实现如下：

首先，我们定义一个函数 `matrixChainOrder` 来计算矩阵链乘法的最小代价和最优断点数。该函数的输入参数为一个整数数组 `p`，其中 `p[i]` 表示第 `i` 个矩阵的行数和第 `i+1` 个矩阵的列数。输出参数为一个二维数组 `s`，其中 `s[i][j]` 表示从第 `i` 个矩阵到第 `j` 个矩阵之间的最优断点数。

void matrixChainOrder(int p[], int n, int **s) {
    int m[n][n];
    for (int i = 1; i < n; i++) {
        m[i][i] = 0;
    }
    for (int l = 2; l < n; l++) {
        for (int i = 1; i < n-l+1; i++) {
            int j = i + l - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j-1; k++) {
                int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
}

在上述函数中，我们首先定义了一个二维数组 `m`，其中 `m[i][j]` 表示从第 `i` 个矩阵到第 `j` 个矩阵之间的最小代价。然后，我们通过两层循环来计算 `m` 数组的值。在内层循环中，我们枚举了所有可能的断点位置 `k`，计算出从第 `i` 个矩阵到第 `k` 个矩阵和从第 `k+1` 个矩阵到第 `j` 个矩阵之间的最小代价，然后加上两个矩阵相乘的代价 `p[i-1]*p[k]*p[j]`，得到从第 `i` 个矩阵到第 `j` 个矩阵之间的总代价 `q`。最后，我们选择代价最小的断点位置 `k`，将其保存到数组 `s` 中。

最后，我们可以通过如下代码来输出最优断点数：

void printOptimalParens(int **s, int i, int j) {
    if (i == j) {
        cout << "A" << i;
    }
    else {
        cout << "(";
        printOptimalParens(s, i, s[i][j]);
        printOptimalParens(s, s[i][j]+1, j);
        cout << ")";
    }
}

在上述代码中，我们通过递归调用 `printOptimalParens` 函数来输出最优断点数。首先，如果 `i` 等于 `j`，那么说明只有一个矩阵，直接输出 `A[i]` 即可。否则，我们在输出左括号后递归地输出左子树和右子树，最后再输出右括号。其中，左子树的范围是从第 `i` 个矩阵到第 `s[i][j]` 个矩阵，右子树的范围是从第 `s[i][j]+1` 个矩阵到第 `j` 个矩阵。

完整代码如下：