MATRIX CHAIN MULTIPLICATION – Full Exam-Ready Notes

(15–20 Marks Guaranteed – Most Important DP Question After Knapsack!)

1. PROBLEM STATEMENT (Write This First – 3 Marks)

Given a sequence of matrices: A₁, A₂, …, An
We need to multiply them: A₁ × A₂ × … × An
Matrix multiplication is associative → many ways to parenthesize
Goal: Find the most efficient (minimum number of scalar multiplications) way.

Cost of multiplying two matrices
If Aᵢ is p×q and Aᵢ₊₁ is q×r → cost = p × q × r

Example:
A(10×30), B(30×5), C(5×60) → (A×B)×C = 10×30×5 + 10×5×60 = 1500 + 3000 = 4500
A×(B×C) = 30×5×60 + 10×30×60 = 9000 + 18000 = 27000 → much costlier!

2. DP RECURRENCE (Most Important – 5 Marks)

Let dimensions array be: d[0], d[1], …, d[n]
Aᵢ has dimension d[i-1] × d[i]

MCM(i, j) = minimum cost to multiply Aᵢ .. Aⱼ

MCM(i, j) = 0                                     if i = j
           = min over k=i to j-1 { 
               MCM(i, k) + MCM(k+1, j) + d[i-1]×d[k]×d[j]
           }

3. CLASSIC EXAM EXAMPLE (Draw This Table – 10 Marks!)

Matrices: A₁(10×30), A₂(30×5), A₃(5×60), A₄(60×20)
Dimensions: d = [10, 30, 5, 60, 20]
n = 4

DP Table M[i][j]

How to fill (show this in exam):

• M[1][2] = 10×30×5 = 1500
• M[2][3] = 30×5×60 = 9000
• M[3][4] = 5×60×20 = 3600
• M[1][3]: k=1 → 1500 + 10×5×60 = 1500+3000=4500
  k=2 → 9000 + 10×30×60 = 9000+18000=27000 → min = 4500
• M[2][4]: k=2 → 9000 + 30×60×20 = 9000+36000=45000
  k=3 → 3600 + 30×5×20 = 3600+3000=6600 → min = 6600
• M[1][4]: k=1 → M[1][1]+M[2][4] + 10×30×20 = 0+6600+6000 = 12600
  k=2 → M[1][2]+M[3][4] + 10×5×20 = 1500+3600+1000 = 6100
  k=3 → M[1][3]+M[4][4] + 10×60×20 = 4500+0+12000 = 16500 → min = 6100

Final Answer: 6100

Optimal Parenthesization: (A₁×(A₂×A₃))×A₄ ? No → From table: k=2 → (A₁×A₂)×(A₃×A₄)

4. TRACKING OPTIMAL PARENTHESIZATION (5 Marks)

Use S[i][j] table to store best k

Print:
((A₁A₂)(A₃A₄))

5. FULL C CODE (Practical + Theory Exam)

#include<stdio.h>
#define INF 999999

void printParenthesis(int i, int j, int s[][5], char* name) {
    if(i == j) {
        printf("%c", *name++);
        return;
    }
    printf("(");
    printParenthesis(i, s[i][j], s, name);
    printParenthesis(s[i][j]+1, j, s, name);
    printf(")");
}

int mcm(int d[], int n) {
    int m[n][n], s[n][n];
    for(int i=0; i<n; i++) m[i][i] = 0;

    for(int len=2; len<n; len++) {           // chain length
        for(int i=1; i<n-len+1; i++) {
            int j = i+len-1;
            m[i][j] = INF;
            for(int k=i; k<j; k++) {
                int cost = m[i][k] + m[k+1][j] + d[i-1]*d[k]*d[j];
                if(cost < m[i][j]) {
                    m[i][j] = cost;
                    s[i][j] = k;
                }
            }
        }
    }

    printf("Minimum cost = %d\n", m[1][n-1]);
    printf("Optimal parenthesization: ");
    char name = 'A';
    printParenthesis(1, n-1, s, &name);
    printf("\n");

    return m[1][n-1];
}

int main() {
    int d[] = {10, 30, 5, 60, 20};
    int n = 5;
    mcm(d, n);
    return 0;
}
// Output:
// Minimum cost = 6100
// Optimal parenthesization: ((A1A2)(A3A4))

6. COMPLEXITY

• Time: O(n³)
• Space: O(n²)

7. MOST ASKED EXAM QUESTIONS (Copy-Paste!)

Q1 (15 Marks):
Dimensions: 40,20,30,10,30
Find minimum cost and parenthesization
→ Draw 5×5 table → Answer = 26000, ((A₁(A₂A₃))A₄)

Q2 (10 Marks): Why DP is needed? Brute force?
→ Brute force = Catalan number → O(4ⁿ/√n) → exponential
DP = O(n³) → polynomial

Q3 (5 Marks):
| Brute Force | DP |
|-------------|----------|
| Exponential | O(n³) |
| No memory | O(n²) |
| Simple | Optimal |

You are now Matrix Chain Multiplication Master!
Draw the table → fill diagonally → show S table → print parentheses → Full Marks!

Next? Say “LCS” or “LONGEST INCREASING SUBSEQUENCE”!