Full lesson preview

Compute matrix chain multiplication cost

Find the minimum number of scalar multiplications needed to multiply a chain of matrices using dynamic programming.

Python practice25 minDynamic ProgrammingAdvancedLast updated March 29, 2026

Problem statement

Given a sequence of matrices A1, A2, ..., An where matrix Ai has dimensions dims[i-1] x dims[i], determine the minimum number of scalar multiplications needed to compute the product A1 x A2 x ... x An. You are given the array dims of length n+1, where the i-th matrix has dimensions dims[i-1] by dims[i]. Return the minimum number of scalar multiplications required to multiply the chain of matrices. The order of multiplication (parenthesization) can greatly affect the cost. Use dynamic programming to find the optimal order.

Task

Implement an algorithm to compute the minimal scalar multiplication cost for multiplying a sequence of matrices (Matrix Chain Multiplication) using DP (tabulation or memoization).

Examples

Classic example

Input

[40, 20, 30, 10, 30]

Output

26000

There are multiple ways to parenthesize the product; the optimal ordering yields 26000 scalar multiplications.

Input format

A single list of integers dims representing matrix chain dimensions, e.g. [d0, d1, d2, ..., dn].

Output format

An integer representing the minimum number of scalar multiplications required.

Constraints

2 <= len(dims) <= 100 (so up to 99 matrices). Each dimension is a positive integer. Expected algorithmic complexity: O(n^3) time and O(n^2) space for the standard DP solution.

Samples

Sample 1

Input

[10, 20, 30]

Output

6000

Only two matrices (10x20) and (20x30) => cost = 10*20*30 = 6000.