1522. Optimal Binary Search Tree

 

Given a set S = {e1, e2, …, en} of n distinct elements such that e1 < e2 < … < en and considering a binary search tree of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root.

The cost of accessing an element ei of S in a tree cost(ei) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S, (f(e1), f(e2), ..., f(en)), we say that the total cost of a tree is the following summation:

f(e1) * cost(e1) + f(e2) * cost(e2) + … + f(en) * cost(en)

In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree.

 

Input. Contains several instances, one per line. Each line will start with a number n (1 ≤ n ≤ 250), indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), ..., f(en) (0 ≤ f(ei) ≤ 100).

 

Output. For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree.

 

Sample input

Sample output

1 5

3 3 1 7

7 4 10 6 2 3 5 7

6 1 3 5 10 20 30

0

5

49

63

 

 

SOLUTION

dynamic programming

 

Algorithm analysis

Imagine that you have written a translation program and posted it on the Internet. Words are located at the vertices of a binary tree.

After a while, for each word ei (key), you learned the number of requests f(ei) to it. The values f(ei) are marked in yellow. The cost of the current Search Tree is

10 + 4 * 2 + 6 * 2 + 5 + 3 * 2 + 7 * 2 = 55

The question arises: is it possible to change the structure of the tree so that to minimize the indicated cost?

For this example, the Optimal Binary Search Tree has the form:

Its cost is

10 + 4 * 2 + 5 + 3 * 2 + 7 * 2 + 2 * 3 = 49

 

Let Ti,j be the cost of an optimal binary search tree that can be constructed from the elements ei, ei+1, …, ej. Obviously, Ti,i = 0 (the cost of a search tree from one vertex is equal to zero). For i < j, the recurrence takes place:

 

Put the element ek at the root. The cost to build the left subtree is Ti,k-1. The cost to build the right subtree is Tk+1,j. Moreover, since the root of the left subtree is one level below ek, to take into account the cost of the left subtree, it is necessary to add the sum of the frequencies of all its elements, that is, the value . Likewise, when calculating the value of the right subtree, add .

For i > j set Ti,j = 0.

Note also that the solution of the problem optimal binary search tree is similar to solution of the problem optimal matrices multiplication.

 

Example

Consider a set S, with three elements e1 < e2 < e3 with frequencies 3, 1 and 7. The frequencies of the elements can follow in any order. Possible search trees are:

cost of the trees

 

The figures do not show all possible trees, but note that the rightmost tree is optimal, its cost is the smallest among all possible ones and equals to 5.

 

Consider the fourth test. The optimal binary search tree has the form:

Then

The cost of the left subtree (if 10 is the root):

T1,4 = 5 + 3 * 2 + 1 * 3 = 14

The cost of the right subtree (if 30 is the root): T6,6 = 0.

 

If the required minimum is attained for k = 5, then

 = (1 + 3 + 5 + 10) + 14 + (30) + 0 = 63,

which equals to the cost of the entire tree.

 

Algorithm realization

Declare the constants.

 

#define MAX 300

#define INF 0x3F3F3F3F

 

Declare the arrays.

 

int m[MAX], sum[MAX];

int t[MAX][MAX];

 

Store the input frequencies of the elements in the array m, the array sum will store the partial sums of the frequencies: sum[i] = . The values Ti,j will be stored in array t.

Partial sum  is returned by the function weight(i, j).

 

int weight(int i, int j)

{

  if (i > j) return 0;

  return sum[j] - sum[i-1];

}

 

Function go(i, j) returns the value of Ti,j.

 

int go(int i, int j)

{

  if (i > j) return 0;

  if (t[i][j] == INF)

  {

    for (int k = i; k <= j; k++)

    {

      int temp = go(i,k-1) + go(k+1,j) + weight(i,k-1) + weight(k+1,j);

      if (temp < t[i][j]) t[i][j] = temp;

    }

  }

  return t[i][j];

}

 

The main part of the program. Read the frequencies of elements, set t[i][i] = Ti,i = 0. The rest of the values of array t are set to infinity.

 

while(scanf("%d",&n) == 1)

{

  memset(t,0x3F,sizeof(t));

  for(i = 1; i <= n; i++)

  {

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

    t[i][i] = 0;

  }

 

Compute the partial sums of array m.

 

  sum[0] = 0

  for(i = 1; i <= n; i++)

    sum[i] = sum[i-1] + m[i];

 

Compute the value of T1,n making the call go(1, n). Print the answer.

 

  go(1,n);

  printf("%d\n",t[1][n]);

}

 

Java realization

 

import java.util.*;

 

public class Main

{

  static int t[][], sum[];

 

  static int weight(int i, int j)

  {

    if (i > j) return 0;

    return sum[j] - sum[i-1];

  }

 

  static int go(int i, int j)

  {

    int k, temp;

    if (i > j) return 0;

    if (t[i][j] == Integer.MAX_VALUE)

    {

      for (k = i; k <= j; k++)

      {

        temp = go(i,k-1) + go(k+1,j) + weight(i,k-1) + weight(k+1,j);

        if (temp < t[i][j]) t[i][j] = temp;

      }

    }

    return t[i][j];

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    while(con.hasNextInt())

    {

      int n = con.nextInt();

      t = new int[n+1][n+1];

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

        Arrays.fill(t[i], Integer.MAX_VALUE);

 

      int m[] = new int[n+1];

      sum = new int[n+1];

     

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

      {

        m[i] = con.nextInt();

        t[i][i] = 0;

      }

     

      sum[0] = 0;

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

        sum[i] = sum[i-1] + m[i];

     

      go(1,n);

      System.out.println(t[1][n]);

    }

    con.close();

  }

}