Dynamic Programming for Matrix Chain Multiplication

1. Understanding the Problem

Imagine you have a chain of matrices to multiply, say A * B * C * D. Matrix multiplication is associative, meaning you can group the multiplications in any way you like, e.g., ((A*B)*C)*D or (A*(B*C))*D. While the final result matrix will be the same, the total number of scalar multiplications (the computational cost) can vary dramatically depending on the parenthesization. Our goal is to find the ordering that minimizes this total cost.

The Cost of Multiplication

First, let's recall how matrices are multiplied. To multiply a matrix M1 of dimensions p x q and a matrix M2 of dimensions q x r, the number of scalar multiplications required is p * q * r. The resulting matrix will have dimensions p x r.

The video below explains this rule and provides a clear example showing why the order of multiplication matters.

Problem Formulation

In a typical problem setup, you aren't given the matrices themselves, but an array of their dimensions. For N-1 matrices, you will be given an array arr of size N. The dimensions of the i-th matrix (1-indexed) are given by arr[i-1] x arr[i].

For example, if arr = [10, 20, 30, 40], we have N=4, which represents N-1=3 matrices:

• M1: 10 x 20 (arr[0] x arr[1])
• M2: 20 x 30 (arr[1] x arr[2])
• M3: 30 x 40 (arr[2] x arr[3])

Our task is to find the minimum number of scalar multiplications to compute M1 * M2 * M3.

2. Devising a Strategy: Partition DP

The MCM problem fits a pattern called Partition DP. The general idea is to take a problem on a range [i, j] and try every possible way to split it into two subproblems.

The strategy is:

1. Start with the entire block/range. For our problem, this is the full chain of matrices, say from matrix i to matrix j.
2. Try all partitions. We can place the last multiplication at any point k between i and j. This splits the problem into two independent subproblems: multiplying matrices (i...k) and multiplying matrices (k+1...j).
3. Return the best possible result. We calculate the cost for each split point k and take the minimum. The total cost for a split at k is: (cost to solve subproblem 1) + (cost to solve subproblem 2) + (cost to multiply their results).

Let's watch a video that outlines this generic approach and begins to formalize it for MCM.

3. From Recursion to Memoization (Top-Down DP)

Let's formalize the recursive solution. We can define a function solve(i, j) that returns the minimum cost to multiply matrices from index i to j.

• Base Case: If i >= j, we have one or zero matrices. The cost is 0.

• Recursive Step: We iterate a partition point k from i to j-1. For each k, we split the chain into (i...k) and (k+1...j). The cost for this partition is:
  solve(i, k) + solve(k+1, j) + cost_to_multiply_results

  The cost to multiply the two resulting matrices is arr[i-1] * arr[k] * arr[j]. (The result of (i...k) is a matrix of size arr[i-1] x arr[k], and the result of (k+1...j) is a matrix of size arr[k] x arr[j]).

This plain recursive solution is extremely slow (exponential time) because it recalculates the same subproblems (solve(i,j) for the same i and j) repeatedly. We can optimize this using memoization.

We'll use a 2D array, dp[i][j], to store the result of solve(i, j). Before computing, we check if dp[i][j] already has a stored value. If so, we return it; otherwise, we compute, store, and then return.

The following resource provides a clear, commented Java implementation of this memoized approach.

The memoized solution has:

• Time Complexity: O(N³) - There are O(N²) states (i, j). For each state, we run a loop for k that takes O(N) time.
• Space Complexity: O(N²) for the DP table, plus O(N) for the recursion stack depth.

4. The Tabulation Approach (Bottom-Up DP)

For interview settings and competitive programming, it's often best to use the iterative tabulation method. It avoids recursion overhead and makes the space complexity more explicit.

The idea is to solve for smaller chains first and use those results to build solutions for larger chains.

1. Initialize a dp[N][N] table.
2. The cost of multiplying a single matrix is 0, so dp[i][i] = 0 for all i. This is our base case.
3. We iterate over the length of the chain, len, from 2 up to N-1.
4. For each length, we iterate through all possible start indices i. The end index j is then i + len - 1.
5. Inside this loop, we apply the same recurrence as before: iterate a partition point k from i to j-1 and find the minimum cost.

dp[i][j] = min(dp[i][k] + dp[k+1][j] + arr[i-1] * arr[k] * arr[j]) for k from i to j-1.

The following video brilliantly explains this conversion from the memoized solution to the tabulated one.

The final answer will be in dp[1][N-1] (if using 1-based indexing for matrices) or dp[0][N-1] (if using 0-based array indexing for the arr of dimensions, which is more common in Java).

The image below, from the classic CLRS textbook, shows what the dp table (labeled m) looks like after being filled by the tabulation algorithm. The algorithm fills the table diagonally, moving away from the main diagonal, corresponding to solving for increasing chain lengths.

Conclusion

You have successfully learned how to solve the Matrix Chain Multiplication problem, a cornerstone of dynamic programming. This lesson introduced you to the powerful Partition DP pattern, which you can apply to a variety of problems involving optimal splitting of intervals.

Key Takeaways:

• Problem: Find the minimum number of scalar multiplications to multiply a chain of matrices. The parenthesization matters.
• Pattern: This is a classic Partition DP problem. The core idea is to define a function solve(i, j) and iterate through all possible split points k within that range.
• Recurrence Relation: cost(i, j) = min_{i <= k < j} { cost(i, k) + cost(k+1, j) + cost_of_combining }.
• Implementation: You can solve this with a top-down (memoized recursion) or bottom-up (tabulation) approach. Both have O(N³) time and O(N²) space complexity.
• Tabulation Strategy: The bottom-up approach iteratively solves for increasing chain lengths, which is a common and efficient way to handle interval-based DP problems.

Preview of the Next Lesson:
We've spent a lot of time on Dynamic Programming, a powerful technique for finding optimal solutions. In the next lesson, we will switch gears to another important algorithmic paradigm: Greedy Algorithms. We will explore problems like Activity Selection and Fractional Knapsack, learning when a greedy choice can lead to a global optimum, which is often faster and simpler than a full DP solution.