Matrix Chain Multiplication
exact_matchHardby cg
dpoptimizationmath
Description
Given a sequence of matrices, find the most efficient way to multiply them together. The problem is not to actually perform the multiplications, but to decide the order (parenthesization) that minimizes the total number of scalar multiplications. Given dimensions [p0, p1, ..., pn], matrix i has dimensions p[i-1] x p[i]. Return the minimum number of scalar multiplications needed.
Input Specification
A JSON object with key:
"dimensions": array of integers [p0, p1, ..., pn] — matrix i is p[i-1] x p[i]
Example: {"dimensions": [10, 30, 5, 60]}Output Specification
A single integer: the minimum number of scalar multiplications. Example: 4500