Matrix Chain Order

Problem

Given dims = [p0, p1, ..., pn] describing n matrices where matrix i has shape p[i-1] by p[i], return the minimum number of scalar multiplications needed to multiply the whole chain.

Use interval dynamic programming: for each subchain try every split point k and add the cost dims[i-1] * dims[k] * dims[j] to the two subproblems. Return 0 when fewer than two matrices are given.

Hint

The final multiplication for a split at k costs dims[i-1] * dims[k] * dims[j] regardless of the two sub-results.

Test cases

case 1

in: [[10,20,30]]

expected: 6000

case 2

in: [[40,20,30,10,30]]

expected: 26000

case 3

in: [[10,30,5,60]]

expected: 4500

case 4

in: [[10,20]]

expected: 0

case 5

in: [[5,10,3]]

expected: 150

Starter codePython

def matrix_chain_order(dims):
    # Your code here
    pass

5 test cases · run your code against them in the editor