Studio Matrix Chain Problem

Studio Matrix Chain Problem — ExecCode Hard DSA Practice

Solve the Studio Matrix Chain problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A film studio multiplies a chain of matrices. The i-th matrix is dims[i] x dims[i+1]. Parenthesizing different ways changes the scalar multiply count. Interval DP computes the minimum; Knuth optimization applies because the cost is quadrangle-inequality friendly. Return the minimum number of scalar multiplications to compute the product of the whole chain. One matrix (or none) costs 0. You are given: dims — length = matrices+1, consecutive dimensions Return minimum multiply count. Only the count is required, not the actual parenthesization.

Examples

Input {'dims': [1, 2, 3, 4]}; Output 18. Input {'dims': [10, 20]}; Output 0. Input {'dims': [2, 2, 2]}; Output 8

Constraints

dims[i] > 0 2 matrices: one product dims[0]dims[1]dims[2]

Practice Studio Matrix Chain free on ExecCode. Browse DSA problems, topic map, and placement guides.