DP 48. Matrix Chain Multiplication | MCM | Partition DP Starts

This chapter marks the introduction of Partition DP, one of the most advanced and nuanced patterns in Dynamic Programming. We begin our study of partition-based problems by examining the classic Matrix Chain Multiplication (MCM) problem, learning how to break down arrays into sub-segments, explore all possible partition points, and optimize the multiplication sequence.

1. Why Do We Need Partition DP? (The Status Quo)

In previous chapters, we mastered 1D DP, 2D DP, DP on grids, and DP on subsequences. However, those patterns do not apply when a problem requires us to break a sequence into smaller parts, solve each part independently, and combine their results in a way where different partitioning strategies yield vastly different outcomes.

Real-Life Analogy: Mathematical Expressions and Parentheses

Consider the simple mathematical expression:

• If we evaluate it as $(1 + 2) \times 3$, the result is $3 \times 3 = 9$.
• If we evaluate it as $1 + (2 \times 3)$, the result is $1 + 6 = 7$.

Whenever a problem asks us to evaluate or solve a sequence in multiple possible ways and find the best possible (minimum or maximum) outcome, we are dealing with Partition DP.

2. Core Mental Model of Partition DP

In Partition DP, we are given an entire array or sequence representing a problem space. Instead of processing elements one by one from left to right, we consider a range defined by a starting index $i$ and an ending index $j$:

Array / Sequence: [ ... element_i ... element_k | element_{k+1} ... element_j ... ]
                     ^                           ^                       ^
                     |                           |                       |
                 Start (i)                  Partition (k)            End (j)

• We place a partition point $k$ somewhere between $i$ and $j$ ($i \le k < j$).
• This divides the main problem into two independent sub-problems:
  1. Left Sub-problem: Range from $i$ to $k$ -> f(i, k)
  2. Right Sub-problem: Range from $k+1$ to $j$ -> f(k+1, j)
• We try all possible partition points $k$, solve both sub-problems for each $k$, and combine their costs to find the optimal (minimum) answer.

3. The Basics of Matrix Multiplication

Before solving MCM, let's review how matrix multiplication works and how operation costs are calculated.

Matrix Dimensions and Multiplication Rules

Given two matrices $A$ and $B$:

• Matrix $A$ has dimensions $R_1 \times C_1$
• Matrix $B$ has dimensions $R_2 \times C_2$
• Multiplication is possible if and only if: $C_1 = R_2$ (the column count of the first matrix equals the row count of the second matrix).
• Resultant Matrix Size: $R_1 \times C_2$
• Number of Multiplication Operations Required: $R_1 \times C_1 \times C_2$

Concrete Example

Suppose we have three matrices $A$, $B$, and $C$ with dimensions:

• $A$: $10 \times 30$
• $B$: $30 \times 5$
• $C$: $5 \times 60$

How many operations does it take to multiply them? There are two primary ways to group them:

1. Grouping $(A \times B) \times C$:

   • Multiply $A$ ($10 \times 30$) and $B$ ($30 \times 5$) $\rightarrow$ Cost = $10 \times 30 \times 5 = 1,500$ operations.
   • Resultant matrix $AB$ has size $10 \times 5$.
   • Multiply $AB$ ($10 \times 5$) and $C$ ($5 \times 60$) $\rightarrow$ Cost = $10 \times 5 \times 60 = 3,000$ operations.
   • Total Operations: $1,500 + 3,000 = 4,500$ operations.

2. Grouping $A \times (B \times C)$:

   • Multiply $B$ ($30 \times 5$) and $C$ ($5 \times 60$) $\rightarrow$ Cost = $30 \times 5 \times 60 = 9,000$ operations.
   • Resultant matrix $BC$ has size $30 \times 60$.
   • Multiply $A$ ($10 \times 30$) and $BC$ ($30 \times 60$) $\rightarrow$ Cost = $10 \times 30 \times 60 = 18,000$ operations.
   • Total Operations: $9,000 + 18,000 = 27,000$ operations.

Conclusion: Matrix multiplication is associative, but not commutative in terms of cost. Grouping $(A \times B) \times C$ takes 4,500 operations, whereas $A \times (B \times C)$ takes 27,000 operations. Our goal in MCM is to find the minimum possible operations across all valid parenthesizations.

4. Problem Statement: Matrix Chain Multiplication (MCM)

Given an array of dimensions representing $N$ matrices where the dimensions of the $i$-th matrix are given by $arr[i-1] \times arr[i]$:

• Matrix 1: $arr[0] \times arr[1]$
• Matrix 2: $arr[1] \times arr[2]$
• Matrix 3: $arr[2] \times arr[3]$
• ...
• Matrix $i$: $arr[i-1] \times arr[i]$

Task: Find the minimum number of scalar multiplication operations needed to compute the product of the chain of matrices.

5. Step-by-Step Design of the Recursive Solution

Following the Partition DP rules, we design our recursive function f(i, j):

Rule 1: Start with the Entire Block

• The entire chain of matrices spans from index $1$ to $N-1$ in the dimension array.
• Therefore, our initial function call is f(1, n - 1), representing the minimum operations required to multiply matrices from matrix $1$ to matrix $n-1$.

Rule 2: Base Case (When to Stop)

• As we partition the array, the ranges (i, j) shrink.
• The smallest possible valid sub-problem is when $i = j$, which represents a single matrix.
• A single matrix requires 0 multiplications.
• Base Case Code:
  C++

  Copy

  if (i == j) return 0;
  

Rule 3: Try All Partitions Using a Loop

• We run a loop for the partition point $k$ from $i$ up to $j - 1$:
  C++

  Copy

  for (int k = i; k < j; k++) {
      // Cost to solve left part: f(i, k)
      // Cost to solve right part: f(k + 1, j)
      // Cost to multiply the two resultant matrices together
  }
  

Calculating the Combination Cost

When we partition at $k$, we divide the range into two blocks:

1. Left block: Matrix $i$ to Matrix $k$, resulting in a matrix of dimension $arr[i-1] \times arr[k]$.
2. Right block: Matrix $k+1$ to Matrix $j$, resulting in a matrix of dimension $arr[k] \times arr[j]$.
3. The cost to multiply these two resultant matrices is:

Thus, the total cost for a specific partition $k$ is:

We take the minimum cost over all possible choices of $k$:

6. Naive Recursive Implementation (TLE)

Here is the initial recursive implementation in C++:

#include <bits/stdc++.h>
using namespace std;

int f(int i, int j, vector<int>& arr) {
    // Base case: single matrix requires 0 operations
    if (i == j) return 0;
    
    int mini = INT_MAX;
    
    // Try every possible partition point k
    for (int k = i; k < j; k++) {
        int steps = (arr[i - 1] * arr[k] * arr[j]) 
                  + f(i, k, arr) 
                  + f(k + 1, j, arr);
                  
        mini = min(mini, steps);
    }
    
    return mini;
}

int matrixMultiplication(vector<int>& arr, int N) {
    return f(1, N - 1, arr);
}

Time Complexity: Exponential ($\mathcal{O}(2^n)$ or worse), leading to Time Limit Exceeded (TLE) on online judges due to overlapping sub-problems.

7. Optimizing with Memoization (Top-Down DP)

Identifying Overlapping Sub-Problems

When drawing the recursion tree for MCM, identical ranges (e.g., multiplying matrices from index $3$ to $4$) are computed repeatedly across different parenthesization branches.

State Representation

• The state of a sub-problem is uniquely defined by two changing variables: i and j.
• Since $i$ and $j$ range from $1$ to $N-1$, we can use a 2D DP table of size $N \times N$ initialized to $-1$.

Memoized Implementation in C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    int f(int i, int j, vector<int>& arr, vector<vector<int>>& dp) {
        // Base case: single matrix
        if (i == j) return 0;
        
        // Return cached result if already computed
        if (dp[i][j] != -1) return dp[i][j];
        
        int mini = 1e9;
        
        // Try all partitions
        for (int k = i; k < j; k++) {
            int steps = (arr[i - 1] * arr[k] * arr[j]) 
                      + f(i, k, arr, dp) 
                      + f(k + 1, j, arr, dp);
                      
            mini = min(mini, steps);
        }
        
        return dp[i][j] = mini;
    }

public:
    int matrixMultiplication(vector<int>& arr, int N) {
        vector<vector<int>> dp(N, vector<int>(N, -1));
        return f(1, N - 1, arr, dp);
    }
};

8. Complexity Analysis of Memoized Solution

9. Summary and Key Takeaways

• Partition DP Definition: Used when a problem can be broken down into sub-segments, and exploring different partition points yields varying optimal costs.
• Problem Range Representation: Always represent the state using a start pointer $i$ and an end pointer $j$ (f(i, j)).
• Initial Function Call: For MCM with an array of size $N$, we start by evaluating the entire block from f(1, N - 1).
• Base Case: When $i == j$, there is only a single matrix, requiring 0 operations.
• Partition Loop: Iterate $k$ from $i$ to $j - 1$, dividing the problem into f(i, k) and f(k + 1, j).
• Cost Formula: The combining cost at partition $k$ is given by $\text{arr}[i-1] \times \text{arr}[k] \times \text{arr}[j]$.
• Overlapping Sub-problems: Pure recursion results in exponential time complexity, which is optimized to $\mathcal{O}(N^3)$ using Memoization with a 2D DP table.