C++矩阵链动态规划二维数组传参及段错误问题求解

现存问题汇总 #

你当前的代码触发段错误、传参失败是多个问题共同导致的：

• 非法使用未初始化变量定义数组：C++标准不支持用变量定义数组长度（变长数组是C99特性，部分编译器扩展支持但不稳定），且你定义int m[i][j], s[i][j],p[i]时i、j都是未初始化的垃圾值，直接申请内存必然越界触发段错误。
• 二维数组传参语法错误：C++原生二维数组作为参数传递时，必须指定除第一维外的所有维度长度，你的int s[][]写法不符合语法要求。
• 逻辑漏洞过多：p数组未赋值、k循环位置错误、最优值比较逻辑位置错误、无穷大赋值类型错误等。

修复后可运行代码 #

推荐用STL的vector替代原生数组，彻底解决二维数组传参的边界问题：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 直接传vector引用，不需要指定维度
void printparanthesis(const vector<vector<int>>& s, int i, int j, char &name)
{
    if (i == j) {
        cout << name++;
        return;
    }
    cout << "(";
    printparanthesis(s, i, s[i][j], name);
    printparanthesis(s, s[i][j]+1, j, name);
    cout << ")";
}
void matrixorder(int ar[], int n)
{
    int i, j, l, k, q;
    vector<int> p(ar, ar + n + 1);
    // 初始化指定大小的二维数组，下标从1到n方便计算
    vector<vector<int>> m(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));
    // l是矩阵链长度
    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;
                    s[i][j] = k;
                }
            }
        }
    }
    char name = 'A';
    cout << "最优括号化方案：";
    printparanthesis(s, 1, n, name);
    cout << endl << "最优成本：" << m[1][n] << endl;
}
int main() {
    int ar[] = {4,10,3,12,20,7};
    int n = sizeof(ar)/sizeof(ar[0]);
    matrixorder(ar, n-1);
    return 0;
}

关键修改说明 #

• 替换原生二维数组为vector<vector<int>>：传参时直接传引用即可，不需要手动指定维度，自动适配矩阵大小，彻底解决原生数组传参的边界限制问题。
• 修正所有逻辑错误：调整循环嵌套顺序、补全p数组赋值、修正最优值更新逻辑、用正确的整数最大值INT_MAX初始化成本数组。
• 运行输出结果为：

  最优括号化方案：((A(BC))(DE))
  最优成本：1344
  

内容的提问来源于stack exchange，提问作者Harsh Mohan Sason