Chapter 1 introduced the MCM skeleton. This chapter fills in the one line that was left abstract: tempAns. For Matrix Chain Multiplication specifically, that line becomes the cost of multiplying two groups of matrices together after splitting the chain at position k.
Everything else — the i, j boundaries, the k loop, the recursion into both halves, the min aggregation — comes directly from Chapter 1.
The Problem
You're given an array of dimensions representing a chain of matrices.
arr = [40, 20, 30, 10, 30]
Matrix A1: 40 × 20 (arr[0] × arr[1])
Matrix A2: 20 × 30 (arr[1] × arr[2])
Matrix A3: 30 × 10 (arr[2] × arr[3])
Matrix A4: 10 × 30 (arr[3] × arr[4])
The matrices must be multiplied in order — you can't rearrange them. But you can choose where to put the parentheses, and different parenthesizations have different costs.
(A1 × A2) × (A3 × A4)
A1 × (A2 × (A3 × A4))
(A1 × (A2 × A3)) × A4
All three produce the same result matrix. But the number of scalar multiplications required is different for each. Find the parenthesization with the minimum cost.
How Matrix Multiplication Cost Works
To multiply a matrix of dimensions a × b by a matrix of dimensions b × c, you perform a × b × c scalar multiplications, and the result is a × c.
A = 40 × 20
B = 20 × 30
A × B costs: 40 × 20 × 30 = 24,000
Result: 40 × 30
This formula — arr[i-1] × arr[k] × arr[j] — becomes the combining cost in the MCM recurrence.
How the Array Represents the Matrices
This indexing is important and trips people up.
Matrix Ai has dimensions: arr[i-1] × arr[i]
A1 = arr[0] × arr[1]
A2 = arr[1] × arr[2]
A3 = arr[2] × arr[3]
A4 = arr[3] × arr[4]
If arr has n elements, there are n-1 matrices. For arr = [40, 20, 30, 10, 30] with n = 5, there are 4 matrices.
This is why the initial call is solve(1, n-1) not solve(0, n-1). The matrices are indexed 1 through n-1, not 0 through n-1.
Applying the MCM Skeleton
From Chapter 1, the skeleton is:
def solve(i, j):
if i >= j: return 0
ans = INF
for k in range(i, j):
left = solve(i, k)
right = solve(k + 1, j)
tempAns = left + right + cost(i, k, j) ← fill this in
ans = min(ans, tempAns)
return ans
For Matrix Chain Multiplication, cost(i, k, j) is the cost of multiplying the result of the left group with the result of the right group.
After solve(i, k), the left group produces a matrix of dimensions arr[i-1] × arr[k].
After solve(k+1, j), the right group produces a matrix of dimensions arr[k] × arr[j].
Multiplying these two together costs: arr[i-1] × arr[k] × arr[j].
So:
tempAns = solve(i, k) + solve(k + 1, j) + arr[i-1] * arr[k] * arr[j]
That's the only line that needed to be determined. The rest was already in the skeleton.
The Full Recurrence
solve(i, j) = minimum cost to multiply matrices Ai through Aj
Base case:
if i >= j: return 0 (one matrix or less — no multiplication needed)
Transition:
for k in range(i, j):
tempAns = solve(i, k) + solve(k + 1, j) + arr[i-1] * arr[k] * arr[j]
ans = min(ans, tempAns)
The Recursive Solution
class Solution:
def solve(self, arr, i, j):
# Base case: one matrix or invalid range — no cost
if i >= j:
return 0
ans = float('inf')
# Try every possible split point
for k in range(i, j):
# Cost of left group + cost of right group + cost of combining them
tempAns = (
self.solve(arr, i, k)
+ self.solve(arr, k + 1, j)
+ arr[i - 1] * arr[k] * arr[j]
)
ans = min(ans, tempAns)
return ans
def matrixMultiplication(self, arr):
n = len(arr)
return self.solve(arr, 1, n - 1)
This works correctly but is slow. The same (i, j) pair appears in multiple branches of the recursion. For example, solve(2, 3) might be computed once when k=1 calls solve(2, 4) which calls solve(2, 3), and again from a different path. Memoization fixes this.
Adding Memoization
The state is (i, j). The table is (n × n) initialised to -1. The k loop is not part of the state — it's just how we explore all options for a given (i, j).
class Solution:
def matrixMultiplication(self, arr):
n = len(arr)
# -1 = not computed yet (0 is a valid cost, so can't use 0)
T = [[-1] * n for _ in range(n)]
def solve(i, j):
# Base case
if i >= j:
return 0
# Return stored answer if already computed
if T[i][j] != -1:
return T[i][j]
ans = float('inf')
for k in range(i, j):
tempAns = (
solve(i, k)
+ solve(k + 1, j)
+ arr[i - 1] * arr[k] * arr[j]
)
ans = min(ans, tempAns)
T[i][j] = ans
return ans
return solve(1, n - 1)
The memoization check (if T[i][j] != -1) is placed before the loop. If (i, j) was already solved, return the stored answer immediately without re-running the loop.
Note: -1 is the sentinel because 0 is a valid answer (a single matrix has zero multiplication cost). The same reasoning applies here as it did in Coin Change I and Count of Subsets from the Knapsack series.
A Partial Dry Run
arr = [40, 20, 30, 10, 30]
Call: solve(1, 4)
k = 1: A1 | A2 A3 A4
left = solve(1, 1) = 0
right = solve(2, 4) = ...
cost = arr[0] * arr[1] * arr[4] = 40 * 20 * 30 = 24,000
k = 2: A1 A2 | A3 A4
left = solve(1, 2) = ...
right = solve(3, 4) = ...
cost = arr[0] * arr[2] * arr[4] = 40 * 30 * 30 = 36,000
k = 3: A1 A2 A3 | A4
left = solve(1, 3) = ...
right = solve(4, 4) = 0
cost = arr[0] * arr[3] * arr[4] = 40 * 10 * 30 = 12,000
The final answer is min of tempAns across all three values of k. The recursive calls compute the internal costs. The answer for arr = [40, 20, 30, 10, 30] is 26,000.
MCM Pattern Checklist for This Problem
| Question | Answer |
|---|---|
What is i? |
Left matrix index (1-based) |
What is j? |
Right matrix index (1-based) |
| Base case? | if i >= j: return 0 |
k range? |
range(i, j) |
| Left subproblem? | solve(i, k) |
| Right subproblem? | solve(k+1, j) |
| Combining cost? | arr[i-1] * arr[k] * arr[j] |
| Aggregation? | min |
Quick Revision
arr = dimensions array, n = len(arr), n-1 matrices
Matrix Ai = arr[i-1] × arr[i]
Initial call: solve(1, n-1)
Base case: if i >= j: return 0
Transition:
for k in range(i, j):
tempAns = solve(i,k) + solve(k+1,j) + arr[i-1]*arr[k]*arr[j]
ans = min(ans, tempAns)
Memoization: T[i][j], initialised to -1
Why -1: 0 is a valid answer (single matrix costs 0)
What You Now Understand
The MCM skeleton from Chapter 1 applied directly. The only new work was identifying that the combining cost is arr[i-1] * arr[k] * arr[j] — the cost of multiplying the result of the left group with the result of the right group. Everything else was already written.
The next chapter applies the same skeleton to Palindrome Partitioning: given a string, find the minimum number of cuts to partition it into palindromes. The tempAns changes, the base case changes slightly, and the aggregation stays min. The structure doesn't change at all.
Top comments (0)