Matrix Chain Multiplication [Optimal Solution]

// CSE245 LAB-06
// Maxtrix Chain Multiplication - Optimal Solution
// Given a sequence of dimensions of "N" number of matrices, find the least number of multiplication required to obtain the product of these matrices and also find the optimal parenthesization.

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#define TAB 7
#define SIZE 100

using namespace std;

int M[SIZE][SIZE];
int S[SIZE][SIZE];

void matrixChainOrder (int P[], int N) {
    for (int i = 1; i <= N; i++)
        M[i][i] = 0;

    for (int l = 2; l <= N; l++)
        for (int i = 1; i <= N - l + 1; i++) {
            int j = i + l - 1;
            M[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = M[i][k] + M[k + 1][j] + (P[i - 1] * P[k] * P[j]);
                if (q < M[i][j]) {
                    M[i][j] = q;
                    S[i][j] = k;
                }
            }
        }
}


void printOptimalParens(int i, int j) {
    if (i == j)
        cout << " A" << i << " ";
    else {
        cout << "(";
        printOptimalParens (i, S[i][j]);
        printOptimalParens (S[i][j] + 1, j);
        cout << ")";
    }
}


void printTable (int N) {
    cout << "M Table: " << endl;
    for (int i = 0; i < N; i++)
        cout << setw(TAB) << right << i + 1;
    cout << endl;
    for (int i = 0; i < N * TAB + 3; i++)
        cout << "-";
    cout << endl;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            cout << setw(TAB)  << right << M[i][j];
        cout << "  | " << setw(TAB)  << left << i;
        cout << endl;
    }
    cout << endl << endl;

    cout << "S Table: " << endl;
    for (int i = 2; i <= N; i++)
        cout << setw(TAB) << right << i;
    cout << endl;
    for (int i = 0; i < N * TAB - 4; i++)
        cout << "-";
    cout << endl;
    for (int i = 1; i < N; i++) {
        for (int j = 2; j <= N; j++)
            cout << setw(TAB) << right << S[i][j];
        cout << "  | " << setw(TAB) << left << i;
        cout << endl;
    }
    cout << endl << endl;
}



int main() {
    string line;
    cout << "Enter the P Values: ";
    getline(cin, line);

    istringstream iss(line);
    int N = -1;
    int P[SIZE];
    while (iss >> line)
        stringstream(line) >> P[++N];

    matrixChainOrder(P, N);
    cout << "Optiimal Parenthesis: ";
    printOptimalParens(1, N);
    cout << endl << endl;

    printTable(N);
    return 0;
}