How should I practice Minimum Matrix-Chain Multiplications?

Start by reading the full statement, solve the visible examples, then compare the pattern against related GSA Capital phone screen problems in FastPrep.

Is Minimum Matrix-Chain Multiplications associated with GSA Capital?

FastPrep tags this as a GSA Capital phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Minimum Matrix-Chain Multiplications

Learn this problem

● Hard

GSA CapitalFULLTIMEPHONE SCREEN

Problem statement

An ordered chain contains n compatible matrices. Matrix i has dimensions dimensions[i - 1] x dimensions[i]. Matrix multiplication is associative, so the final product is unchanged by parenthesization, but the number of scalar multiplications may differ.

Return the minimum scalar-multiplication count needed to multiply the entire chain. Do not materialize the matrices.

Function

minimumMultiplications(dimensions: int[]) → long

Examples

Example 1

dimensions = [40,20,30,10,30]return = 26000

The best order is ((A1 x (A2 x A3)) x A4), with cost 6000 + 8000 + 12000 = 26000.

Example 2

dimensions = [10,20,30]return = 6000

Two matrices have only one possible multiplication order, costing 10 x 20 x 30 = 6000.

Example 3

dimensions = [10,30,5,60]return = 4500

Multiplying the first two matrices before the third costs 1500 + 3000 = 4500.

Constraints

2 <= dimensions.length <= 101
Every dimension is a positive integer.
Every scalar product and every intermediate candidate sum evaluated by the recurrence is less than 2^62.