Matrix Chain Multiplication: Making the Skeleton Concrete

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. 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. 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. 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. 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]. 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. 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) 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. 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. 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. 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 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) 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.