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 – Try with Resources
Hướng dẫn Java Design Pattern – State
Guide to Java 8 groupingBy Collector
HTTP Authentification and CGI/Servlet
Java Program to Implement K Way Merge Algorithm
Java Program to Implement Triply Linked List
Java Program to Implement Heap
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Most commonly used String methods in Java
Guide to the Synchronized Keyword in Java
Spring Autowiring of Generic Types
Spring WebFlux Filters
Spring Cloud – Tracing Services with Zipkin
Java Program to find the number of occurrences of a given number using Binary Search approach
Get and Post Lists of Objects with RestTemplate
Transactions with Spring and JPA
Guide to the Volatile Keyword in Java
Guide to Mustache with Spring Boot
Creating a Web Application with Spring 5
Shuffling Collections In Java
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Java Program to Implement Ternary Search Algorithm
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
How to Get the Last Element of a Stream in Java?
Java Program to Solve TSP Using Minimum Spanning Trees
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Java Program to Implement Pairing Heap
Java Program to Implement Stein GCD Algorithm
Truyền giá trị và tham chiếu trong java
Mapping a Dynamic JSON Object with Jackson
Convert Time to Milliseconds in Java
A Quick Guide to Spring MVC Matrix Variables