DP 49: Matrix Chain Multiplication | Bottom-Up | Tabulation

1. Why Do We Need Tabulation for MCM?

In the previous memoization approach for Matrix Chain Multiplication (MCM), we successfully eliminated exponential recalculations by storing overlapping subproblem results. However, the solution was only partially accepted in competitive programming platforms.

The Core Issue: Even with memoization, the recursive engine consumes auxiliary stack space proportional to the maximum depth of the recursion tree. To achieve 100% acceptance and optimal performance, we must eliminate recursion entirely by transitioning to an iterative bottom-up tabulation approach, reducing auxiliary space to just the DP table itself ($O(N^2)$).

2. Core Mental Model: Top-Down vs. Bottom-Up

Understanding how to invert a recursive strategy into an iterative loop requires contrasting the traversal direction:

Real-Life Analogy: Building a Brick Wall

Building from the ground up: Imagine constructing a multi-story brick wall. In top-down recursion, you visualize the entire finished skyscraper and ask sub-teams to build smaller sections from the top down. In bottom-up tabulation, you lay down the foundation bricks first (base cases), cement adjacent pairs next, and systematically stack row upon row until the entire structure is complete without ever needing a blueprint stack in your head.

3. The 3 Golden Rules of Tabulation

Converting any memoized Dynamic Programming solution to tabulation follows three universal steps:

1. Copy the Base Cases: Initialize the DP table directly with boundary conditions without changing their logic.
2. Identify Changing Parameters: Determine the loop boundaries for state variables (i and j) by analyzing the direction of subproblem dependencies.
3. Copy the Recurrence Relation: Translate the recursive transition choice and cost addition logic into iterative loops, replacing function calls f(i, j) with table lookups dp[i][j].

4. Step 1: Base Case Initialization

In our MCM problem, the base case occurs when a subproblem involves multiplying a single matrix by itself (i.e., when index i equals index j).

• Meaning: The minimum cost required to multiply a single matrix from index i to i is 0 because no multiplication operations are needed.
• Code representation:
  C++

  Copy

  // Initialize DP table of size n x n with zeros
  vector<vector<int>> dp(n, vector<int>(n, 0));
  
  // Base cases: cost of multiplying a single matrix with itself is 0
  for (int i = 1; i < n; i++) {
      dp[i][i] = 0;
  }
  

5. Step 2: Determining Loop Boundaries (The Practical Shift)

In the recursive top-down approach, parameters started from i = 1 and j = n - 1 and moved inward toward base cases. In bottom-up tabulation, we must compute smaller intervals before larger intervals.

Analyzing the Constraints on i and j:

• Matrix order invariant: In matrix chain multiplication, index i must always stay to the left of index j (i < j), because a valid chain spans from matrix i to matrix j.
• Loop for i: Since the top-down recursion initialized i starting from n - 1 down towards smaller values, our bottom-up outer loop for i runs in reverse:
  C++

  Copy

  for (int i = n - 1; i >= 1; i--)
  

• Loop for j: Rather than running j blindly from 0 to n - 1, we must be practical: j represents the right boundary, so it must always start to the right of i (i + 1) and advance up to n - 1:
  C++

  Copy

  for (int j = i + 1; j < n; j++)
  

6. Step 3: Translating the Recurrence Relation

Recall the recursive choice from our memoized solution where we partitioned the chain at every possible index k (ranging from i to j - 1) to find the minimum multiplication cost:

In tabulation, we replace the recursive function calls with direct accesses to our dp table:

int mini = INT_MAX;
for (int k = i; k < j; k++) {
    int steps = dp[i][k] + dp[k + 1][j] + (arr[i - 1] * arr[k] * arr[j]);
    mini = min(mini, steps);
}
dp[i][j] = mini;

7. Complete Bottom-Up Tabulation Code

Putting all three steps together gives us the final, production-ready C++ tabulation solution.

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

int matrixMultiplication(vector<int>& arr, int n) {
    // Create a DP table of size n x n initialized to 0
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Step 1: Base Case Initialization
    // dp[i][i] is already 0 by default, but we can explicitly iterate if needed:
    for (int i = 1; i < n; i++) {
        dp[i][i] = 0;
    }

    // Step 2 & 3: Fill the DP table bottom-up
    // i starts from n - 1 down to 1
    for (int i = n - 1; i >= 1; i--) {
        // j starts from i + 1 up to n - 1
        for (int j = i + 1; j < n; j++) {
            int mini = 1e9; // Initialize to a very large number (infinity)

            // Partition loop trying every split point k between i and j-1
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + (arr[i - 1] * arr[k] * arr[j]);
                mini = min(mini, cost);
            }

            dp[i][j] = mini;
        }
    }

    // The final answer for multiplying matrix 1 to n-1
    return dp[1][n - 1];
}

8. Complexity Analysis

Summary and Key Takeaways

• Eliminating Stack Overflow: Bottom-up tabulation replaces recursive function calls with iterative loops, entirely removing auxiliary stack space overhead and preventing stack overflow errors.
• The Three-Step Rule: Converting any DP problem to tabulation involves copying base cases, setting correct loop boundaries for changing parameters, and translating recurrence relations into table lookups.
• Direction Matters: In interval DP problems like MCM, loop bounds must mirror dependency flows—computing smaller intervals before larger intervals (i goes downwards from n-1 to 1, j goes outwards from i+1 to n-1).
• Practical Loop Boundaries: Always respect problem invariants (e.g., i must always remain to the left of j, meaning j must start at i + 1).
• Optimal Complexity: Achieves $O(N^3)$ time complexity and $O(N^2)$ space complexity, making it fully accepted in competitive programming and production-grade software systems.