Matrix Chain Multiplication

Matrix Chain Multiplication (MCM)

1. Algorithm Explanation

Matrix Chain Multiplication (MCM) is a classic Dynamic Programming problem that deals with finding the most efficient way to multiply a given sequence of matrices. The goal is to determine the minimum number of scalar multiplications needed to multiply the entire chain.

Problem Statement:

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of scalar multiplications.

Matrices are compatible for multiplication if the number of columns in one equals the number of rows in the next. Given an array p[] of size n, where the i-th matrix has dimensions p[i-1] x p[i].

Dynamic Programming Approach:

  1. Let dp[i][j] represent the minimum number of multiplications to compute the product of matrices from index i to j.
  2. Initialize dp[i][i] = 0 for all i.
  3. Fill the table using increasing chain lengths.
  4. For each chain length and each subproblem, find the minimum cost by placing parenthesis at all possible positions.

Time and Space Complexity:

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

2. Easy Problems

Problem 1: Minimum cost of multiplying a chain of matrices

<!-- C++ code -->
#include <iostream>
#include <climits>
using namespace std;

int matrixChainOrder(int p[], int n) {
    int dp[n][n];
    for (int i = 1; i < n; i++) dp[i][i] = 0;

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[1][n - 1];
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum multiplications: " << matrixChainOrder(arr, n);
    return 0;
}

Problem 2: Count number of ways to parenthesize the product

<!-- C++ code -->
#include <iostream>
using namespace std;

int countWays(int n) {
    int dp[n][n] = {0};
    for (int i = 1; i < n; i++) dp[i][i] = 1;

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                dp[i][j] += dp[i][k] * dp[k + 1][j];
            }
        }
    }
    return dp[1][n - 1];
}

int main() {
    int n = 4; // 3 matrices
    cout << "Ways to parenthesize: " << countWays(n);
    return 0;
}

3. Intermediate Problems

Problem 1: Optimal Binary Search Tree (OBST)

This can be solved using a similar dynamic programming approach to MCM.

<!-- C++ code -->
#include <iostream>
#include <climits>
using namespace std;

int optimalBST(int keys[], int freq[], int n) {
    int dp[n][n];

    for (int i = 0; i < n; i++) dp[i][i] = freq[i];

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            int sum = 0;
            for (int k = i; k <= j; k++) sum += freq[k];

            for (int r = i; r <= j; r++) {
                int cost = ((r > i) ? dp[i][r - 1] : 0) +
                           ((r < j) ? dp[r + 1][j] : 0) + sum;
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys) / sizeof(keys[0]);
    cout << "Cost of OBST: " << optimalBST(keys, freq, n);
    return 0;
}

Problem 2: Boolean Parenthesization

<!-- C++ code -->
#include <iostream>
#include <cstring>
using namespace std;

int dp[101][101][2];

int countWays(string s, int i, int j, bool isTrue) {
    if (i > j) return 0;
    if (i == j) {
        if (isTrue) return s[i] == 'T';
        else return s[i] == 'F';
    }

    if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue];

    int ans = 0;
    for (int k = i + 1; k <= j - 1; k += 2) {
        int lt = countWays(s, i, k - 1, true);
        int lf = countWays(s, i, k - 1, false);
        int rt = countWays(s, k + 1, j, true);
        int rf = countWays(s, k + 1, j, false);

        if (s[k] == '&') {
            ans += isTrue ? (lt * rt) : (lt * rf + lf * rt + lf * rf);
        } else if (s[k] == '|') {
            ans += isTrue ? (lt * rt + lt * rf + lf * rt) : (lf * rf);
        } else if (s[k] == '^') {
            ans += isTrue ? (lt * rf + lf * rt) : (lt * rt + lf * rf);
        }
    }
    return dp[i][j][isTrue] = ans;
}

int main() {
    string s = "T|F&T^T";
    memset(dp, -1, sizeof(dp));
    cout << "Ways to parenthesize to True: " << countWays(s, 0, s.size() - 1, true);
    return 0;
}

4. Hard Problem

Problem: Evaluate Expression to get Minimum Cost (MCM Variant)

Given an array of numbers and operations (e.g., +, *, -), compute the minimum result by changing the parenthesis. Similar to MCM, use DP with cost evaluation based on operation type.

<!-- C++ code -->
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int eval(int a, int b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    return a * b;
}

pair<int, int> minMax(vector<int>& nums, vector<char>& ops, int i, int j,
                      vector<vector<int>>& minDp, vector<vector<int>>& maxDp) {
    if (i == j) return {nums[i], nums[i]};
    if (minDp[i][j] != INT_MAX) return {minDp[i][j], maxDp[i][j]};

    int mn = INT_MAX, mx = INT_MIN;
    for (int k = i; k < j; ++k) {
        auto left = minMax(nums, ops, i, k, minDp, maxDp);
        auto right = minMax(nums, ops, k + 1, j, minDp, maxDp);

        for (int a : {left.first, left.second})
            for (int b : {right.first, right.second}) {
                int val = eval(a, b, ops[k]);
                mn = min(mn, val);
                mx = max(mx, val);
            }
    }

    minDp[i][j] = mn;
    maxDp[i][j] = mx;
    return {mn, mx};
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<char> ops = {'+', '*', '-'};
    int n = nums.size();

    vector<vector<int>> minDp(n, vector<int>(n, INT_MAX));
    vector<vector<int>> maxDp(n, vector<int>(n, INT_MIN));

    auto res = minMax(nums, ops, 0, n - 1, minDp, maxDp);
    cout << "Minimum value: " << res.first << ", Maximum value: " << res.second;
    return 0;
}