#include <stdio.h>
#include <limits.h>

#define INF INT_MAX

// Function to find the value of k that minimizes the cost in c[i, j]
int Find(double c[][10], int r[][10], int i, int j) {
    int min = INF, k;
    for (int m = r[i][j-1]; m <= r[i+1][j]; m++) {
        int cost = c[i][m-1] + c[m][j];
        if (cost < min) {
            min = cost;
            k = m;
        }
    }
    return k;
}

// Function to compute the optimal binary search tree
void OBST(int n, double p[], double q[], double c[][10], int r[][10], double w[][10]) {
    // Initialize arrays
    for (int i = 0; i <= n; i++) {
        w[i][i] = q[i];
        r[i][i] = 0;
        c[i][i] = 0.0;
    }

    // For trees with 1 node
    for (int i = 0; i < n; i++) {
        w[i][i+1] = q[i] + q[i+1] + p[i+1];
        r[i][i+1] = i+1;
        c[i][i+1] = q[i] + q[i+1] + p[i+1];
    }

    // Calculate cost, root, and weight for larger trees
    for (int m = 2; m <= n; m++) {
        for (int i = 0; i <= n - m; i++) {
            int j = i + m;

            w[i][j] = w[i][j-1] + p[j] + q[j];
            
            // Find the optimal root for the tree [i, j]
            int k = Find(c, r, i, j);
            
            c[i][j] = w[i][j] + c[i][k-1] + c[k][j];
            r[i][j] = k;
        }
    }

    // Output the results for the optimal binary search tree
    printf("Optimal cost: %.2f\n", c[0][n]);
    printf("Optimal root: %d\n", r[0][n]);
    for (int i = 0; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            printf("c[%d][%d] = %.2f, w[%d][%d] = %.2f, r[%d][%d] = %d\n", i, j, c[i][j], i, j, w[i][j], i, j, r[i][j]);
        }
    }
}

int main() {
    int n = 4;  // Number of identifiers (for example: do, if, int, while)
    double p[] = {0, 3, 3, 1, 1};  // Probabilities of searching for the identifiers
    double q[] = {0, 2, 3, 1, 1, 1};  // Probabilities of unsuccessful searches

    double c[10][10] = {0};  // Cost matrix
    int r[10][10] = {0};  // Root matrix
    double w[10][10] = {0};  // Weight matrix

    OBST(n, p, q, c, r, w);

    return 0;
}
********************
  OUPUT

Optimal cost: 32.00
Optimal root: 2
c[0][1] = 8.00, w[0][1] = 8.00, r[0][1] = 1
c[0][2] = 19.00, w[0][2] = 12.00, r[0][2] = 1
c[0][3] = 25.00, w[0][3] = 14.00, r[0][3] = 2
c[0][4] = 32.00, w[0][4] = 16.00, r[0][4] = 2
c[1][2] = 7.00, w[1][2] = 7.00, r[1][2] = 2
c[1][3] = 12.00, w[1][3] = 9.00, r[1][3] = 2
c[1][4] = 19.00, w[1][4] = 11.00, r[1][4] = 2
c[2][3] = 3.00, w[2][3] = 3.00, r[2][3] = 3
c[2][4] = 8.00, w[2][4] = 5.00, r[2][4] = 3
c[3][4] = 3.00, w[3][4] = 3.00, r[3][4] = 4