Task-6
Implement OBST using dynamic programming
Algorithm:
Algorithm OBST(p, q, n)
// Given n distinct identifiers a1 < a2 < ··· < an and probabilities
// p[i], 1 ≤ i ≤ n, and q[i], 0 ≤ i ≤ n, this algorithm computes
// the cost c[i, j] of optimal binary search tree for identifiers
// a_i, ..., a_j. It also computes r[i, j], the root of t[i, j].
// w[i, j] is the weight of t[i, j].
{
  for i := 0 to n do
  { 
    // Initialize.
    w[i, i] := q[i]; r[i, i] := 0; c[i, i] := 0.0;
    // Optimal trees with one node
    w[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
    c[i, i + 1] := w[i, i + 1]; r[i, i + 1] := i + 1;
  }
  
  for m := 2 to n do // Find optimal trees with m nodes.
    for i := 0 to n - m do
    {
      j := i + m;
      w[i, j] := w[i, j - 1] + p[j] + q[j];
      c[i, j] := ∞; // Solve 5.12 using Knuth's result.
      k := Find(c, r, i, j);
      // A value of k in the range [r[i, j - 1], r[i + 1, j]] that minimizes c[i, k - 1] + c[k, j];
      c[i, j] := w[i, j] + c[i, k - 1] + c[k, j];
      r[i, j] := k;
    }
  write (c[0, n], w[0, n], r[0, n]);
}

Algorithm Find(c, r, i, j)
{
  min := ∞;
  for m := r[i, j - 1] to r[i + 1, j] do
    if (c[i, m - 1] + c[m, j] < min) then
    {
      min := c[i, m - 1] + c[m, j];
      l_i := m;
    }
  return l_i;
}

Program:
#include <stdio.h>
#define MAX 10
#define INF 300000

void main() {
    char ele[MAX][MAX];
    int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX];
    int p[MAX], q[MAX];
    int temp, min, min1;
    int i, j, k, b, n;

    // Input number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // Input probabilities for elements p[i]
    for (i = 1; i <= n; i++) {
        printf("Enter the element P(%d): ", i);
        scanf("%d", &p[i]);
    }
    printf("\n");

    // Input probabilities for dummy keys q[i]
    for (i = 0; i <= n; i++) {
        printf("Enter the element q(%d): ", i);
        scanf("%d", &q[i]);
    }
    printf("\n");

    printf("W \t\t C \t\t R\n");

    // Initialization of w, c, and r matrices for single elements
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            if (i == j) {
                w[i][i] = q[i];
                c[i][i] = 0;
                r[i][i] = 0;
                printf("w[%d][%d] : %d \t c[%d][%d]: %d \t r[%d][%d] : %d\n", i, j, w[i][j], i, j, c[i][j], i, j, r[i][j]);
            }
        }
    }
    printf("\n");

    // Fill w, c, and r matrices for ranges [i, j]
    for (b = 0; b < n; b++) {
        for (i = 0, j = b + 1; j <= n; i++, j++) {
            if (i != j && i < j) {
                // Calculate w[i][j]
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                min = INF;

                // Find minimum cost and root for this subproblem
                for (k = i + 1; k <= j; k++) {
                    min1 = c[i][k - 1] + c[k][j] + w[i][j];
                    if (min > min1) {
                        min = min1;
                        temp = k;
                    }
                }

                // Store minimum cost and root for this range
                c[i][j] = min;
                r[i][j] = temp;
            }
            // Print w[i][j], c[i][j], and r[i][j]
            printf("w[%d][%d] : %d \t c[%d][%d]: %d \t r[%d][%d] : %d\n", i, j, w[i][j], i, j, c[i][j], i, j, r[i][j]);
        }
        printf("\n");
    }

    // Print minimum cost for the entire tree
    printf("Minimum cost: %d\n", c[0][n]);
}
Output:
/tmp/VsdNZE6fYV.o
Enter the number of elements: 4
Enter the element P(1): 3
Enter the element P(2): 3
Enter the element P(3): 1
Enter the element P(4): 1

Enter the element q(0): 2
Enter the element q(1): 3
Enter the element q(2): 1
Enter the element q(3): 1
Enter the element q(4): 1

W 		 C 		 R
w[0][0] : 2 	 c[0][0]: 0 	 r[0][0] : 0
w[1][1] : 3 	 c[1][1]: 0 	 r[1][1] : 0
w[2][2] : 1 	 c[2][2]: 0 	 r[2][2] : 0
w[3][3] : 1 	 c[3][3]: 0 	 r[3][3] : 0
w[4][4] : 1 	 c[4][4]: 0 	 r[4][4] : 0

w[0][1] : 8 	 c[0][1]: 8 	 r[0][1] : 1
w[1][2] : 7 	 c[1][2]: 7 	 r[1][2] : 2
w[2][3] : 3 	 c[2][3]: 3 	 r[2][3] : 3
w[3][4] : 3 	 c[3][4]: 3 	 r[3][4] : 4

w[0][2] : 12 	 c[0][2]: 19 	 r[0][2] : 1
w[1][3] : 9 	 c[1][3]: 12 	 r[1][3] : 2
w[2][4] : 5 	 c[2][4]: 8 	 r[2][4] : 3

w[0][3] : 14 	 c[0][3]: 25 	 r[0][3] : 2
w[1][4] : 11 	 c[1][4]: 19 	 r[1][4] : 2

w[0][4] : 16 	 c[0][4]: 32 	 r[0][4] : 2

Minimum cost: 32


=== Code Exited With Errors ===