public class OptimalBST {
  public static void main(String[] args) {
      double p[] = { 0.00, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14 };
      double q[] = { 0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05 };
    int n = p.length - 1;

    System.out.println("n= " + n + "\n");
    
    double e[][] = new double[n+2][n+1];
    double w[][] = new double[n+2][n+1];
    int raiz[][] = new  int  [n+2][n+1];

    for (int i = 1; i <= n+1; i++) {
        e[i][i-1] = q[i-1];
        w[i][i-1] = q[i-1];
      }

    for (int l = 1; l <= n; l++) {
      System.out.println("Para comprimento l=" + l + "\n");

      for (int i = 1; i <= (n - l + 1); i++) {
	  int j = i + l - 1;
        e[i][j] = java.lang.Integer.MAX_VALUE;
	w[i][j] = w[i][j-1] + p[j] + q[j];

        System.out.println("- Para i=" + i + ", j=" + j + ":");

        for (int r = i; r <= j; r++) {
	    double t = e[i][r-1] + e[r+1][j] + w[i][j];

          System.out.println("--- Para r=" + r + ", t=" + t);

          if (t < e[i][j]) {
            e[i][j] = t;
            raiz[i][j] = r;
          }
        }
        System.out.print("\n");
      }
      System.out.print("\n");
    }

    // Matriz e
    System.out.println("\n\nMatriz e\n");
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
        System.out.print(e[i][j] + " ");
      System.out.println("");
    }

    // Matriz w
    System.out.println("\nMatriz w\n");
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
        System.out.print(w[i][j] + " ");
      System.out.println("");
    }

    // Matriz raiz
    System.out.println("\nMatriz raiz\n");
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
        System.out.print(raiz[i][j] + " ");
      System.out.println("");
    }
  }
}