Java Program to Perform Optimal Parenthesization Using Dynamic Programming

«
»
This is a java program to perform optimal paranthesization by making use of dymanic programming. This program determines the order in which the chain of matrices should be multiplied.

Here is the source code of the Java Program to Perform Optimal Paranthesization Using Dynamic Programming. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. package com.sanfoundry.numerical;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class OptimalParanthesizationUsingDP
  6. {
  7.     private int[][] m;
  8.     private int[][] s;
  9.     private int     n;
  10.  
  11.     public OptimalParanthesizationUsingDP(int[] p)
  12.     {
  13.         n = p.length - 1; // how many matrices are in the chain
  14.         m = new int[n + 1][n + 1]; // overallocate m, so that we don't use index
  15.                                    // 0
  16.         s = new int[n + 1][n + 1]; // same for s
  17.         matrixChainOrder(p); // run the dynamic-programming algorithm
  18.     }
  19.  
  20.     private void matrixChainOrder(int[] p)
  21.     {
  22.         // Initial the cost for the empty subproblems.
  23.         for (int i = 1; i <= n; i++)
  24.             m[i][i] = 0;
  25.         // Solve for chains of increasing length l.
  26.         for (int l = 2; l <= n; l++)
  27.         {
  28.             for (int i = 1; i <= n - l + 1; i++)
  29.             {
  30.                 int j = i + l - 1;
  31.                 m[i][j] = Integer.MAX_VALUE;
  32.                 // Check each possible split to see if it's better
  33.                 // than all seen so far.
  34.                 for (int k = i; k < j; k++)
  35.                 {
  36.                     int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
  37.                     if (q < m[i][j])
  38.                     {
  39.                         // q is the best split for this subproblem so far.
  40.                         m[i][j] = q;
  41.                         s[i][j] = k;
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.     }
  47.  
  48.     private String printOptimalParens(int i, int j)
  49.     {
  50.         if (i == j)
  51.             return "A[" + i + "]";
  52.         else
  53.             return "(" + printOptimalParens(i, s[i][j])
  54.                     + printOptimalParens(s[i][j] + 1, j) + ")";
  55.     }
  56.  
  57.     public String toString()
  58.     {
  59.         return printOptimalParens(1, n);
  60.     }
  61.  
  62.     public static void main(String[] args)
  63.     {
  64.         Scanner sc = new Scanner(System.in);
  65.         System.out
  66.                 .println("Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]");
  67.         System.out.println("Enter the total length: ");
  68.         int n = sc.nextInt();
  69.         int arr[] = new int[n];
  70.         System.out.println("Enter the dimensions: ");
  71.         for (int i = 0; i < n; i++)
  72.             arr[i] = sc.nextInt();
  73.         OptimalParanthesizationUsingDP opudp = new OptimalParanthesizationUsingDP(
  74.                 arr);
  75.         System.out.println("Matrices are of order: ");
  76.         for (int i = 1; i < arr.length; i++)
  77.         {
  78.             System.out.println("A" + i + "-->" + arr[i - 1] + "x" + arr[i]);
  79.         }
  80.         System.out.println(opudp.toString());
  81.         sc.close();
  82.     }
  83. }

Output:

advertisement
$ javac OptimalParanthesizationUsingDP.java
$ java OptimalParanthesizationUsingDP
 
Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]
Enter the total length: 
5
Enter the dimensions: 
2 4 5 2 1 
Matrices are of order: 
A1-->2x4
A2-->4x5
A3-->5x2
A4-->2x1
(A[1](A[2](A[3]A[4])))

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.