aaa

package sample;

// A naive recursive implementation of optimal binary
// search tree problem
public class Algo
{
        /* A Dynamic Programming based function that calculates
            minimum cost of a Binary Search Tree.  */
        static int optimalSearchTree(int keys[], int freq[], int n) {

        /* Create an auxiliary 2D matrix to store results of
           subproblems */
            int cost[][] = new int[n + 1][n + 1];
            int root[][] = new int[n + 1][n + 1];


        /* cost[i][j] = Optimal cost of binary search tree that
           can be formed from keys[i] to keys[j]. cost[0][n-1]
           will store the resultant cost */

            // For a single key, cost is equal to frequency of the key
            for (int i = 0; i < n; i++)
                cost[i][i] = freq[i];

            printTable(cost,n);


            // Now we need to consider chains of length 2, 3, ... .
            // L is chain length.
            for (int L = 2; L <= n; L++) {

                // i is row number in cost[][]
                for (int i = 0; i <= n - L + 1; i++) {

                    // Get column number j from row number i and
                    // chain length L
                    int j = i + L - 1;
                    cost[i][j] = Integer.MAX_VALUE;

                    // Try making all keys in interval keys[i..j] as root
                    for (int r = i; r <= j; r++) {

                        // c = cost when keys[r] becomes root of this subtree
                        int ll = 0;
                        int rr = 0;
                        int sm = sum(freq, i, j);
                        int c = 0;
                        if (r > i)
                            ll = cost[i][r - 1];
                        else
                            ll = 0;
                        //
                        if (r < j)
                            rr += cost[r + 1][j];
                        else
                            rr += 0;
                        //
                        c = ll + rr + sm;
                        if (c < cost[i][j]) {
                            cost[i][j] = c;
                            System.out.println("ll:"+ll+"\trr:"+rr+"\tsum:"+sm);
                        }
                    }
                    System.out.println("cost["+i+"]["+j+"] = "+cost[i][j]);
                }
                printTable(cost,n);

            }
            printTable(cost,n);
            return cost[0][n - 1];
        }

        static void printTable(int cost[][],int n){
            for (int i=0;i<n;i++){
                for (int i2=0;i2<n;i2++)
                    System.out.print(cost[i][i2]+"\t");
                System.out.println("");
            }
            System.out.println("");
        }

        // A utility function to get sum of array elements
        // freq[i] to freq[j]
        static int sum(int freq[], int i, int j) {
            int s = 0;
            for (int k = i; k <= j; k++) {
                if (k >= freq.length)
                    continue;
                s += freq[k];
            }
            return s;
        }

        public static void main(String[] args) {

            //int keys[] = { 10, 12, 20};
            //int freq[] = { 34, 8, 50 };
            int keys[] = {10,12,16,21};
            int freq[] = {4,2,6,3};
            int n = keys.length;

            for (int i = 0;i<n;i++)
                System.out.print(i+"\t");
            System.out.println("");
            for (int i = 0;i<n;i++)
                System.out.print(keys[i]+"\t");
            System.out.println("");
            for (int i = 0;i<n;i++)
                System.out.print(freq[i]+"\t");
            System.out.println("\n\n");

            System.out.println("Cost of Optimal BST is "
                    + optimalSearchTree(keys, freq, n));
        }

}
//This code is contributed by Sumit Ghosh