JavaAlgorithms/DynamicProgramming/MatrixChainMultiplication.java

package DynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class MatrixChainMultiplication {
  private static Scanner scan = new Scanner(System.in);
  private static ArrayList<Matrix> mArray = new ArrayList<>();
  private static int size;
  private static int[][] m;
  private static int[][] s;
  private static int[] p;

  public static void main(String[] args) {
    int count = 1;
    while (true) {
      String[] mSize = input("input size of matrix A(" + count + ") ( ex. 10 20 ) : ");
      int col = Integer.parseInt(mSize[0]);
      if (col == 0) break;
      int row = Integer.parseInt(mSize[1]);

      Matrix matrix = new Matrix(count, col, row);
      mArray.add(matrix);
      count++;
    }
    for (Matrix m : mArray) {
      System.out.format("A(%d)  =  %2d  x  %2d%n", m.count(), m.col(), m.row());
    }

    size = mArray.size();
    m = new int[size + 1][size + 1];
    s = new int[size + 1][size + 1];
    p = new int[size + 1];

    for (int i = 0; i < size + 1; i++) {
      Arrays.fill(m[i], -1);
      Arrays.fill(s[i], -1);
    }

    for (int i = 0; i < p.length; i++) {
      p[i] = i == 0 ? mArray.get(i).col() : mArray.get(i - 1).row();
    }

    matrixChainOrder();
    for (int i = 0; i < size; i++) {
      System.out.print("-------");
    }
    System.out.println();
    printArray(m);
    for (int i = 0; i < size; i++) {
      System.out.print("-------");
    }
    System.out.println();
    printArray(s);
    for (int i = 0; i < size; i++) {
      System.out.print("-------");
    }
    System.out.println();

    System.out.println("Optimal solution : " + m[1][size]);
    System.out.print("Optimal parens : ");
    printOptimalParens(1, size);
  }

  private static void printOptimalParens(int i, int j) {
    if (i == j) {
      System.out.print("A" + i);
    } else {
      System.out.print("(");
      printOptimalParens(i, s[i][j]);
      printOptimalParens(s[i][j] + 1, j);
      System.out.print(")");
    }
  }

  private static void printArray(int[][] array) {
    for (int i = 1; i < size + 1; i++) {
      for (int j = 1; j < size + 1; j++) {
        System.out.print(String.format("%7d", array[i][j]));
      }
      System.out.println();
    }
  }

  private static void matrixChainOrder() {
    for (int i = 1; i < size + 1; i++) {
      m[i][i] = 0;
    }

    for (int l = 2; l < size + 1; l++) {
      for (int i = 1; i < size - l + 2; i++) {
        int j = i + l - 1;
        m[i][j] = Integer.MAX_VALUE;

        for (int k = i; k < j; 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;
          }
        }
      }
    }
  }

  private static String[] input(String string) {
    System.out.print(string);
    return (scan.nextLine().split(" "));
  }
}

class Matrix {
  private int count;
  private int col;
  private int row;

  Matrix(int count, int col, int row) {
    this.count = count;
    this.col = col;
    this.row = row;
  }

  int count() {
    return count;
  }

  int col() {
    return col;
  }

  int row() {
    return row;
  }
}