OPTIMAL BINARY SEARCH TREE - DYNAMIC PROGRAMMING

/*
    Optimal BST using dynamic programming approach
    cost[n][n] auxiliary array to store the solution of subproblem
    cost[0][n-1] holds the final result

    First fill all diagonal entries i.e cost[i][i] and then
    values above the diagonal - cost[i][i+1] , cost[i][i+2]

    Uses a chain length variable L and increment it iteratively to calculate
    'j' using 'i' and 'L'

*/

#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;


//utility function to get sum of array withing bounds specified
int sum(int freq[], int i, int j);



//function deploying dynamic programming approcah to calculate minimum cost of
//BST

int optimalSearchTree(int keys[], int freq[], int  n)
{
    int cost[3][3];


    //cost[i][j] is optimal cost of bst formed from keys[i] to keys[j]

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

    //consider chains of length 2, 3 ,..and stuff like this
    //where L would be the chain length

    for (int L = 2; L <= n; ++L)
    {

        for (int i = 0; i < n - L + 1; ++i)
        {
            int j = i + L - 1;
            cost[i][j] = INT_MAX;

       

            //make all key bw interval keys[i..j] as root
            for (int r = i; r <= j; ++r)
            {
                            //c = cost of keys[r] acting as root of this subtree
                int c = ((r > i) ? cost[i][r - 1] : 0) + ((r < j) ? cost[r + 1][j] : 0)
                    + sum(freq, i, j);
                if (c < cost[i][j])
                    cost[i][j] = c;
            }
        }

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


//utility function to get sum of array withing bounds specified
int sum(int freq[], int i, int j)
{
    int s = 0;
    for (int k = i; k <= j; ++k)
        s += freq[k];
    return s;
}

    // Driver program to test above functions
    int main()
    {
        int keys[] = { 10, 12, 20 };
        int freq[] = { 34, 8, 50 };
        int n = sizeof(keys) / sizeof(keys[0]);
        printf("Cost of Optimal BST is %d ", optimalSearchTree(keys, freq, n));
        getchar();
        return 0;
    }