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;
 }
}