6. Write program to implement Dynamic Programming algorithm for the Optimal Binary search tree problem || DAA

 Search Tree Problem. 

#include <stdio.h> 

#include<limits.h> 

#define MAX_KEYS 100 

int optimalBST(int keys[], int freq[], int n) { 

int dp[MAX_KEYS + 1][MAX_KEYS + 1]; 

for (int i = 0; i <= n; i++) { 

for (int j = 0; j <= n; j++) { 

dp[i][j] = 0; 

} 

} 

for (int len = 1; len <= n; len++) { 

for (int i = 0; i <= n - len + 1; i++) { 

int j = i + len - 1; 

dp[i][j] = INT_MAX; 

for (int r = i; r <= j; r++) { 

int c = ((r > i) ? dp[i][r - 1] : 0) + ((r < j) ? dp[r + 1][j] : 0) + freq[r]; 

if (c < dp[i][j]) { 

dp[i][j] = c; 

} 

} 

} 

} 

return dp[0][n - 1]; 

}

int main() { 

int n; 

printf("Enter the number of keys: "); 

scanf("%d", &n); 

int keys[MAX_KEYS], freq[MAX_KEYS]; 

printf("Enter the keys:\n");  

for (int i = 0; i < n; i++)  

{   scanf("%d", &keys[i]); 

} 

printf("Enter the frequencies:\n"); 

for (int i = 0; i < n; i++) { 

scanf("%d", &freq[i]); 

} 

int result = optimalBST(keys, freq, n); 

printf("Optimal cost of a Binary Search Tree: %d\n", result); 

return 0; 

}