cppadvanced15 minutes

Build a Function to Perform Multi-level Memoized Matrix Chain Multiplication

Implement an optimized function to compute the minimum number of scalar multiplications needed to multiply a given chain of matrices using memoization to achieve efficient performance.

Challenge prompt

Given an array 'dims' of length n+1 representing the dimensions of n matrices (the i-th matrix has dimensions dims[i-1] x dims[i]), implement a function 'matrixChainOrder' in C++ that returns the minimum scalar multiplication cost to multiply the chain of matrices from 1 to n. Use dynamic programming with memoization to optimize the recursive solution. Your function signature should be: int matrixChainOrder(const std::vector<int>& dims);.

Guidance

• Use a helper recursive function with memoization that calculates the minimum cost for multiplying matrices from index i to j.
• Store and reuse previously computed results in a 2D memo table to avoid redundant calculations.
• Carefully handle base cases where the chain length is 1 (no multiplication needed).

Hints

• Think about the optimal substructure: the cost for matrices from i to j depends on the optimal split point k where i <= k < j.
• Your memo table should be a 2D vector initialized with a sentinel value (e.g., -1) to denote uncomputed states.
• Iterate through all possible splits k and select the one minimizing the cost of multiplying left and right subchains plus multiplication cost.

Starter code

#include <vector>
#include <iostream>
#include <climits>

int matrixChainOrder(const std::vector<int>& dims) {
    // Implement your memoized solution here
}

int main() {
    std::vector<int> dims = {40, 20, 30, 10, 30};
    std::cout << matrixChainOrder(dims) << std::endl; // Expected output: 26000
    return 0;
}

Expected output

26000

Core concepts

dynamic programmingmemoizationrecursionoptimizationmatrix chain multiplication

Challenge a Friend

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