@@ -0,0 +1,1694 @@
+package com.algorithms.splay;%0A%0Apublic class OptimalBSTHelper %7B%0A%09/* A Dynamic Programming based function that calculates minimum cost of%0A%09   a Binary Search Tree. */%0A%09public static int optimalSearchTree(int keys%5B%5D, int freq%5B%5D, int n)%0A%09%7B%0A%09    /* Create an auxiliary 2D matrix to store results of subproblems */%0A%09    int cost%5B%5D%5B%5D = new int%5Bn%5D%5Bn%5D;%0A%09 %0A%09    /* cost%5Bi%5D%5Bj%5D = Optimal cost of binary search tree that can be%0A%09       formed from keys%5Bi%5D to keys%5Bj%5D.%0A%09       cost%5B0%5D%5Bn-1%5D will store the resultant cost */%0A%09 %0A%09    // For a single key, cost is equal to frequency of the key%0A%09    for (int i = 0; i %3C n; i++)%0A%09        cost%5Bi%5D%5Bi%5D = freq%5Bi%5D;%0A%09 %0A%09    // Now we need to consider chains of length 2, 3, ... .%0A%09    // L is chain length.%0A%09    for (int L=2; L%3C=n; L++)%0A%09    %7B%0A%09        // i is row number in cost%5B%5D%5B%5D%0A%09        for (int i=0; i%3C=n-L+1; i++)%0A%09        %7B%0A%09            // Get column number j from row number i and chain length L%0A%09            int j = i+L-1;%0A%09            cost%5Bi%5D%5Bj%5D = Integer.MAX_VALUE;%0A%09 %0A%09            // Try making all keys in interval keys%5Bi..j%5D as root%0A%09            for (int r=i; r%3C=j; r++)%0A%09            %7B%0A%09               // c = cost when keys%5Br%5D becomes root of this subtree%0A%09               int c = ((r %3E i)? cost%5Bi%5D%5Br-1%5D:0) + %0A%09                       ((r %3C j)? cost%5Br+1%5D%5Bj%5D:0) + %0A%09                       sum(freq, i, j);%0A%09               if (c %3C cost%5Bi%5D%5Bj%5D)%0A%09                  cost%5Bi%5D%5Bj%5D = c;%0A%09            %7D%0A%09        %7D%0A%09    %7D%0A%09    return cost%5B0%5D%5Bn-1%5D;%0A%09%7D%0A%09 %0A%09// A utility function to get sum of array elements freq%5Bi%5D to freq%5Bj%5D%0A%09private static int sum(int freq%5B%5D, int i, int j)%0A%09%7B%0A%09    int s = 0;%0A%09    for (int k = i; k %3C=j; k++)%0A%09       s += freq%5Bk%5D;%0A%09    return s;%0A%09%7D%0A%7D%0A

Add initial OptimalBST dynamic programming solver from geeksforgeeks.com