cppadvanced15 minutes

Fix Bug in Optimized Matrix Chain Multiplication Implementation

The provided C++ code implements the Matrix Chain Multiplication algorithm using dynamic programming to find the minimum number of scalar multiplications needed to multiply a chain of matrices. However, the current implementation contains bugs that lead to incorrect results and occasional runtime errors. Your task is to identify and fix these bugs so the algorithm returns correct and optimized results.

Challenge prompt

You are given a broken implementation of the Matrix Chain Multiplication problem that aims to find the minimum cost of multiplying a sequence of matrices. The input is an array representing the dimensions of the matrices. The function should return the minimum number of scalar multiplications needed. Fix the bugs related to array indexing, loop boundaries, and initialization to ensure correct results and efficient runtime.

Guidance

• Carefully check your indexing in the nested loops controlling subproblems.
• Verify initialization of your DP table so intermediate values are set correctly before computation.
• Trace through a simple example to confirm your fixes result in correct minimum costs.

Hints

• Remember that matrices Ai has dimensions p[i-1] x p[i], so your loops must consider these indices carefully.
• Initialize the diagonal of the cost matrix to zero as multiplying one matrix costs nothing.
• Check the inner loop that partitions the matrix chain — off-by-one errors are common here.

Starter code

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int matrixChainMultiplication(const vector<int> &p) {
    int n = p.size();
    vector<vector<int>> dp(n, vector<int>(n, 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] = INT_MAX;
            for (int k = i; k < j; ++k) {
                int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }
    return dp[1][n - 1];
}

int main() {
    vector<int> dims = {40, 20, 30, 10, 30};
    cout << matrixChainMultiplication(dims) << endl;
    return 0;
}

Expected output

26000

Core concepts

dynamic programmingmatrix chain multiplicationarray indexingalgorithm debugging

Challenge a Friend

Send this duel to someone else and see if they can solve it.