Published by Dimitris Kougioumtzis · Updated
Choose multiplication order with minimum scalar multiplications and reconstruct the parenthesization.
Try every last split of each matrix interval and combine its two optimal subcosts with the boundary-dimension multiplication cost.
When to use Matrix-chain multiplication
Choosing multiplication parenthesization before numeric work.
Choosing an alternative
The algorithm changes grouping, not matrix order.
Worked example: input and state changes
Example input
10,30,5,60
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: A single matrix requires no scalar multiplications.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 3 }Step 1: Interval 0–1: split after 0, candidate 1500, best 1500.
State at this checkpoint
{ "values": [ 0, 1500, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 1 ], "kind": "matrix", "columns": 3 }Step 3: Interval 0–2: split after 0, candidate 27000, best 27000.
State at this checkpoint
{ "values": [ 0, 1500, 27000, 0, 0, 9000, 0, 0, 0 ], "active": [ 2 ], "kind": "matrix", "columns": 3 }Step 4: Interval 0–2: split after 1, candidate 4500, best 4500.
State at this checkpoint
{ "values": [ 0, 1500, 4500, 0, 0, 9000, 0, 0, 0 ], "active": [ 2 ], "kind": "matrix", "columns": 3 }Step 5: Minimum scalar multiplications = 4500; order ((AB)C).
State at this checkpoint
{ "values": [ 0, 1500, 4500, 0, 0, 9000, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 3, "result": 4500, "parenthesization": "((AB)C)" }
Expected final state
Minimum scalar multiplications = 4500; order ((AB)C).
Complexity and input bounds
Family: Dynamic programming. Time complexity: O(n³).
Space complexity: O(n squared) interval costs and splits.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
2–9 matrix dimensions, each 1–99. Matrix i has dimensions d[i] × d[i+1].
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A dimension array has one more entry than the number of matrices; multiplication is not generally commutative.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | // 2–9 positive dimensions ≤ 99. Returns minimum scalar multiplications. output[0] is parenthesization token count; subsequent ASCII codes use matrices A..H and parentheses. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(dims, count, output) { let n = count - 1; let dp = Array(256).fill(0); let split = Array(256).fill(0); for (let length = 2; length <= n; length++) { for (let i = 0; i + length <= n; i++) { let j = i + length - 1; dp[i * n + j] = 1000000000; for (let k = i; k < j; k++) { let cost = dp[i * n + k] + dp[(k + 1) * n + j] + dims[i] * dims[k + 1] * dims[j + 1]; if (cost < dp[i * n + j]) { dp[i * n + j] = cost; split[i * n + j] = k; } } } } let left = Array(256).fill(0); let right = Array(256).fill(0); let type = Array(256).fill(0); let top = 1; let tokens = 0; right[0] = n - 1; while (top > 0) { top--; let l = left[top]; let r = right[top]; let kind = type[top]; if (kind == 1) { output[++tokens] = 41; } else if (l == r) { output[++tokens] = 65 + l; } else { output[++tokens] = 40; let k = split[l * n + r]; left[top] = 0; right[top] = 0; type[top++] = 1; left[top] = k + 1; right[top] = r; type[top++] = 0; left[top] = l; right[top] = k; type[top++] = 0; } } output[0] = tokens; return dp[n - 1]; } |
Source
Foundational dynamic-programming paper. It establishes the general method, not the first publication or exact recurrence of this particular teaching example.
- The theory of dynamic programming
Richard Bellman (1954). Foundational method paper.