Implement the solution to the Optimal Binary Search Tree problem using dynamic programming.?

The Optimal Binary Search Tree (OBST) is a classic problem in dynamic programming, which is aimed at determining the optimal cost of searching for an element in a Binary Search Tree (BST).

Before diving into the DP solution, let’s review some basic concepts related to BST:

- A BST is a binary tree where each node has a key greater than all the keys in the left sub-tree and less than all the keys in the right sub-tree.

- The keys of the BST are such that they will be accessed with some frequency. The more frequently accessed keys should be placed closer to the root of the tree to minimize the search cost.

- The search cost is the sum of the frequencies of all the keys that are accessed during a search.

So, given n keys and their frequencies, the task is to build a Binary Search Tree that has a minimal total search cost.

To solve this problem, we create a 2-D array ‘C[i][j]‘ where ‘0 <= i, j <= n‘ representing the cost of the optimal BST containing keys ‘k[i+1]‘ through ‘k[j]‘ where ‘k‘ is the array of keys sorted in increasing order. We also create a 2-D array ‘W[i][j]‘ for the sum of the frequencies from ‘k[i+1]‘ to ‘k[j]‘.

The base case is ‘C[i][i] = W[i][i]‘ for all ‘0 i n‘.

For i > j, ‘C[i][j] = 0‘ as an empty tree has no cost.

For all i < j, the optimal cost is the minimum cost we can achieve by trying every possible root node in the BST of keys ‘k[i+1]‘ to ‘k[j]‘. This optimal cost is given by the formula:

`C[i][j] = min(C[i][r-1] + C[r+1][j] + W[i][j])` where `i <= r <= j`

The above formula states that to compute the optimal cost for ‘k[i+1]‘ to ‘k[j]‘, we have to consider every possible ‘r‘ as root node and recursively compute the optimal cost for left and right subtrees of ‘r‘, then add the frequency of all nodes in ‘k[i+1]‘ to ‘k[j]‘, which gives ‘W[i][j]‘.

Once we have the above 2-D array ‘C‘, ‘C[0][n]‘ will give us the optimal cost of searching all elements in the BST.

Here’s the Java code implementing the above algorithm:

public static int optimalSearchTree(int[] keys, int[] freq) {
    int n = keys.length;

    // create c[n+1][n+1] and w[n+1][n+1]
    int[][] c = new int[n+1][n+1];
    int[][] w = new int[n+1][n+1];

    // initialize the base case when i=j
    for (int i = 0; i < n; i++) {
        c[i][i] = freq[i];
        w[i][i] = freq[i];
    } 

    // fill in the tables diagonally
    for (int l = 2; l <= n+1; l++) {
        for (int i = 0; i <= n-l+1; i++) {
            int j = i + l - 1;
            w[i][j] = w[i][j-1] + freq[j-1];
            c[i][j] = Integer.MAX_VALUE;

            // compute optimal cost for the subtree rooted at r
            for (int r = i; r <= j; r++) {
                int cost = ((r > i) ? c[i][r-1] : 0) +
                           ((r < j) ? c[r+1][j] : 0) +
                           w[i][j];
                if (cost < c[i][j])
                    c[i][j] = cost;
            }
        }
    }

    return c[0][n-1];
}

The time complexity of the above code is O(n³) which is due to the three nested for-loops. However, since we only have to evaluate ‘n * (n + 1)/2‘ subproblems, the space complexity is O(n²).