Matrix Chain Multiplication

Find the minimum number of scalar multiplications to multiply a chain of matrices.

matrix dynamic-programming optimization interval-dp

Given a list `dims` of positive integers representing matrix dimensions, where matrix `i` has dimensions `dims[i] x dims[i+1]`, the chain is valid if there are at least two matrices, i.e., `len(dims) >= 3`. Write a function `min_mult_cost(dims)` that returns the minimum number of scalar multiplications needed to multiply the entire chain. For example, with `dims = [10, 30, 5, 60]`, there are three matrices: 10x30, 30x5, and 5x60. The optimal parenthesization gives a cost of 4500. If there are fewer than 3 elements in `dims`, return 0. The function must be deterministic and must not rely on external libraries. Implement the dynamic programming solution (either top-down or bottom-up).

Constraints

2 <= len(dims) <= 20 (so at least one matrix; if len < 3 return 0). Each dimension is 1 <= dims[i] <= 1000. The result fits within a 64-bit integer. Complexity: O(n^3) time and O(n^2) space, where n = len(dims) - 1.

Example

>>> min_mult_cost([10, 30, 5, 60])
4500
>>> min_mult_cost([2, 3, 4])
24
>>> min_mult_cost([1])
0

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of subchains from i to j (i inclusive, j exclusive) where i < j.

The cost to multiply a chain i..j is: cost(i,k) + cost(k,j) + dims[i]*dims[k]*dims[j].

Use a 2D table to store costs for increasing chain lengths.

Base case: single matrix (i+1==j) has cost 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.