Optimal binary search tree using dynamic programming

Implementation

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
#include <bits/stdc++.h>
using namespace std;


//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
int sum(int frequency[], int i, int j);


// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
int optCost(int frequency[], int i, int j)
{
	if (j < i) 
		return 0;
	if (j == i) 
		return frequency[i];
	
	//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
	
	// regularizing the minimal value or data.
	int min = INT_MAX;
	
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j);
		if (cost < min)
			min = cost;
	}
	
	// at this step, we have to return the minimal value.
	return min + freqsum;
}


// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of the binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
int Opt_SearchTree(int kys[],
					int frequency[], int n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1);
}


// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
int sum(int frequency[], int i, int j)
{
	int s = 0;
	for (int k = i; k <= j; k++)
	s += frequency[k];
	return s;
}


// writing the main code.
int main()
{
	int kys[] = {10, 12, 20};
	int frequency[] = {34, 8, 50};
	int n = sizeof(kys) / sizeof(kys[0]);
	cout << "Cost of Optimal BST is "
		<< Opt_SearchTree(kys, frequency, n);
	return 0;
}

Output:

Example 2)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
#include <stdio.h>
#include <limits.h>
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
int sum(int frequency[], int i, int j);
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
int optCost(int frequency[], int i, int j)
{
if (j < i)	
	return 0;
if (j == i)	
	return frequency[i];
//In this step, we have to get the sum of the i and i+1…… frequency j. 
int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.
int min = INT_MAX;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
for (int r = i; r <= j; ++r)
{
	int cost = optCost(frequency, i, r-1) +
				optCost(frequency, r+1, j);
	if (cost < min)
		min = cost;
}
	// at this step, we have to return the minimal value.
return min + freqsum;
}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
int Opt_SearchTree(int kys[], int frequency[], int n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n-1);
}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
int sum(int frequency[], int i, int j)
{
	int s = 0;
	for (int k = i; k <=j; k++)
	s += frequency[k];
	return s;
}
// writing the main code.
int main()
{
	int kys[] = {10, 12, 20};
	int frequency[] = {34, 8, 50};
	int n = sizeof(kys)/sizeof(kys[0]);
	printf("Cost of Optimal BST is %d ",
			Opt_SearchTree(kys, frequency, n));
	return 0;
}

Output:

Example 3)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
public class TFG
{
	//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
	static int optCost(int frequency[], int i, int j)
	{
	if (j < i)	 
		return 0;
	if (j == i)
		return frequency[i];
	
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.
	int min = Integer.MAX_VALUE;
// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r-1) +
						optCost(frequency, r+1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + freqsum;
	}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
	static int Opt_SearchTree(int kys[], int frequency[], int n)
	{
			// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
		return optCost(frequency, 0, n-1);
	}
	// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
	static int sum(int frequency[], int i, int j)
	{
		int s = 0;
		for (int k = i; k <=j; k++)
		s += frequency[k];
		return s;
	}
// writing the main code.	
	public static void main(String[] args) {
		int kys[] = {10, 12, 20};
		int frequency[] = {34, 8, 50};
		int n = kys.length;
		System.out.println("Cost of Optimal BST is " +
						Opt_SearchTree(kys, frequency, n));
	}
}

Output:

Example 4)

# We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
def optCost(frequency, i, j):
		if j < i:	
		return 0
	if j == i:	 
		return frequency[i]
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	freqsum = Sum(frequency, i, j)
	
	# regularizing the minimal value or data.
	Min = 999999999999
	
	# We have to start initializing all the data or records one at a time and consider all the elements present in there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for r in range(i, j + 1):
		cost = (optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j))
		if cost < Min:
			Min = cost
	
	# at this step, we have to return the minimal value.


	return Min + freqsum


# Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
def Opt_SearchTree(kys, frequency, n):
	
	# In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1)


# We are creating a utility function to help us get the sum of the frequency of the elements present in that specific array. 
def Sum(frequency, i, j):
	s = 0
	for k in range(i, j + 1):
		s += frequency[k]
	return s


# writing the main code.
if __name__ == '__main__':
	kys = [10, 12, 20]
	frequency = [34, 8, 50]
	n = len(kys)
	print("Cost of Optimal BST is",
		Opt_SearchTree(kys, frequency, n))

Output:

Example 5)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
using System;
class TFG
{
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
	static int optCost(int []frequency, int i, int j)
	{
		
	if (j < i)	
		return 0;
	if (j == i)	
		return frequency[i];
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.	
	int min = int.MaxValue;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r-1) +
						optCost(frequency, r+1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + fsum;
	}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
	static int Opt_SearchTree(int []kys, int []frequency, int n)
	{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
		return optCost(frequency, 0, n-1);
	}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
	static int sum(int []frequency, int i, int j)
	{
		int s = 0;
		for (int k = i; k <=j; k++)
		s += frequency[k];
		return s;
	}
// writing the main code.	
	public static void Main()
	{
		int []kys = {10, 12, 20};
		int []frequency = {34, 8, 50};
		int n = kys.Length;
		Console.Write("Cost of Optimal BST is " +
						Opt_SearchTree(kys, frequency, n));
	}
}

Output:

Example 6)

<script>
// We are creating a Javascript presentation where we will present a recursive method of the optimal binary search tree problem. 
function optCost(frequency, i, j)
{
	if (j < i) 
		return 0;
	if (j == i) 
		return frequency[i];
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	var freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.	
	var min = Number. MAX_SAFE_INTEGER;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (var r = i; r <= j; ++r)
	{
		var cost = optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + fsum;
}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
function Opt_SearchTree(kys, frequency, n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1);
}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
function sum(frequency, i, j)
{
	var s = 0;
	for (var k = i; k <= j; k++)
	s += frequency[k];
	return s;
}




// writing the main code.	
var kys = [10, 12, 20];
var frequency = [34, 8, 50];
var n = kys.length;
document.write("Cost of Optimal BST is " +
	Opt_SearchTree(kys, frequency, n));
	</script>

Output: