Funcia
Lv.3dpinterval-dp

Matrix Chain Multiplication

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Matrix i has size dims[i] × dims[i+1]. Multiplying p × q by q × r costs p·q·r. Return the minimum total cost to multiply the whole chain (order fixed, parenthesisation free), or 0 for a single matrix.

Examples

dimsresult
[10, 30, 5, 60]4500
[40, 20, 30, 10, 30]26000
[7, 3]0

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(dims: int[]) → long

Constraints

  • 2≤2 \le dims.length ≤201\le 201, 1≤1 \le dims[i] ≤1,000\le 1{,}000; the answer can exceed 32 bits.

Expected complexity

Time
O(N^3)
Space
O(N^2)

Examples

dimsExpected
[10,30,5,60]4500
[40,20,30,10,30]26000
[7,3]0

Hint

Hint

Interval DP over chain ranges, shortest ranges first: cost[i][j] = min_k cost[i][k] + cost[k+1][j] + dims[i]·dims[k+1]·dims[j+1]. Unmemoised recursion is exponential.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness406verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.