Multiplication order

Parenthesisation changes matrix chain cost.

Matrix multiplication is associative but cost depends on order. (A1·A2)·A3 and A1·(A2·A3) need different numbers of scalar multiplications.

The goal is to find the parenthesization with the fewest scalar multiplications. This is a classic dynamic programming problem.

Dimension array

Each matrix is described by a dimension pair: Ai has size dims[i-1] × dims[i]. For example dims = [10, 20, 30, 40] gives three matrices.

Multiplying two adjacent matrices takes dims[i-1] × dims[i] × dims[i+1] scalar multiplications. This is the basis of the cost.

Write init_dims(). Return the list [10, 20, 30, 40]. Print it with print(init_dims()).

Show example solution

def init_dims():
    # Return dimension array
    return [10, 20, 30, 40]
print(init_dims())

Next lesson: DP table