Java Program to Perform Optimal Paranthesization 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.

package com.sanfoundry.numerical;
 
import java.util.Scanner;
 
public class OptimalParanthesizationUsingDP
{
    private int[][] m;
    private int[][] s;
    private int     n;
 
    public OptimalParanthesizationUsingDP(int[] p)
    {
        n = p.length - 1; // how many matrices are in the chain
        m = new int[n + 1][n + 1]; // overallocate m, so that we don't use index
                                   // 0
        s = new int[n + 1][n + 1]; // same for s
        matrixChainOrder(p); // run the dynamic-programming algorithm
    }
 
    private void matrixChainOrder(int[] p)
    {
        // Initial the cost for the empty subproblems.
        for (int i = 1; i <= n; i++)
            m[i][i] = 0;
        // Solve for chains of increasing length l.
        for (int l = 2; l <= n; l++)
        {
            for (int i = 1; i <= n - l + 1; i++)
            {
                int j = i + l - 1;
                m[i][j] = Integer.MAX_VALUE;
                // Check each possible split to see if it's better
                // than all seen so far.
                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])
                    {
                        // q is the best split for this subproblem so far.
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
 
    private String printOptimalParens(int i, int j)
    {
        if (i == j)
            return "A[" + i + "]";
        else
            return "(" + printOptimalParens(i, s[i][j])
                    + printOptimalParens(s[i][j] + 1, j) + ")";
    }
 
    public String toString()
    {
        return printOptimalParens(1, n);
    }
 
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out
                .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]");
        System.out.println("Enter the total length: ");
        int n = sc.nextInt();
        int arr[] = new int[n];
        System.out.println("Enter the dimensions: ");
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        OptimalParanthesizationUsingDP opudp = new OptimalParanthesizationUsingDP(
                arr);
        System.out.println("Matrices are of order: ");
        for (int i = 1; i < arr.length; i++)
        {
            System.out.println("A" + i + "-->" + arr[i - 1] + "x" + arr[i]);
        }
        System.out.println(opudp.toString());
        sc.close();
    }
}

Output:

$ 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])))

Related posts:

Java Program to Implement Segment Tree
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
A Guide to Apache Commons Collections CollectionUtils
Lớp Properties trong java
Java Program to Construct an Expression Tree for an Postfix Expression
Java Program to Find the Mode in a Data Set
Java Program to Implement PriorityQueue API
Interface trong Java 8 – Default method và Static method
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Weak References in Java
Hamcrest Collections Cookbook
Java Program to Perform the Sorting Using Counting Sort
Java Program to Implement Gabow Algorithm
A Guide to Java SynchronousQueue
Java Program to Check the Connectivity of Graph Using DFS
Java Program to Implement AttributeList API
Java Program to Implement LinkedList API
Hướng dẫn sử dụng Printing Service trong Java
Giới thiệu thư viện Apache Commons Chain
Spring Cloud AWS – Messaging Support
Java Program to Implement Depth-limited Search
The Modulo Operator in Java
Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching
Custom JUnit 4 Test Runners
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Send email with SMTPS (eg. Google GMail)
Java Program to Compute the Area of a Triangle Using Determinants
The Registration API becomes RESTful
The Registration Process With Spring Security
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Giới thiệu Java 8
Java Program to Represent Graph Using 2D Arrays