Рубрики

Оптимальное бинарное дерево поиска | DP-24

Для заданного отсортированного массива ключей [0 .. n-1] ключей поиска и массива freq [0 .. n-1] частотных отсчетов, где freq [i] — количество запросов к ключам [i] . Создайте двоичное дерево поиска всех ключей так, чтобы общая стоимость всех поисков была как можно меньше.

Давайте сначала определим стоимость BST. Стоимость узла BST — это уровень этого узла, умноженный на его частоту. Уровень корня 1.

Примеры:

Input:  keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs 
        10                       12
          \                     / 
           12                 10
          I                     II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118 


Input:  keys[] = {10, 12, 20}, freq[] = {34, 8, 50}
There can be following possible BSTs
    10                12                 20         10              20
      \             /    \              /             \            /
      12          10     20           12               20         10  
        \                            /                 /           \
         20                        10                12             12  
     I               II             III             IV             V
Among all possible BSTs, cost of the fifth BST is minimum.  
Cost of the fifth BST is 1*50 + 2*34 + 3*8 = 142

1) Оптимальная подструктура:
Оптимальная стоимость для freq [i..j] может быть рекурсивно рассчитана по следующей формуле.

Нам нужно вычислить optCost (0, n-1), чтобы найти результат.

Идея вышеприведенной формулы проста, мы один за другим пробуем все узлы как корень (r изменяется от i до j во втором члене). Когда мы делаем r-й узел корневым, мы рекурсивно вычисляем оптимальную стоимость от i до r-1 и от r + 1 до j.
Мы добавляем сумму частот от i до j (см. Первый термин в приведенной выше формуле), это добавляется потому, что каждый поиск будет проходить через корень, и для каждого поиска будет сделано одно сравнение.

2) Перекрывающиеся подзадачи
Ниже приводится рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

C ++

// Наивная рекурсивная реализация
// задача оптимального бинарного дерева поиска
#include <bits/stdc++.h>

using namespace std;

  
// Функция полезности для получения суммы
// элементы массива от freq [i] до freq [j]

int sum(int freq[], int i, int j); 

  
// Рекурсивная функция для расчета
// стоимость оптимального бинарного дерева поиска

int optCost(int freq[], int i, int j) 

    // Базовые случаи

    if (j < i)  // нет элементов в этом подмассиве

        return 0; 

    if (j == i) // один элемент в этом массиве

        return freq[i]; 

      

    // Получить сумму freq [i], freq [i + 1], ... freq [j]

    int fsum = sum(freq, i, j); 

      

    // Инициализируем минимальное значение

    int min = INT_MAX; 

      

    // один за другим рассмотрим все элементы

    // как корень и рекурсивно найти стоимость

    // BST, сравните стоимость с

    // min и обновляем min при необходимости

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

    

        int cost = optCost(freq, i, r - 1) + 

                   optCost(freq, r + 1, j); 

        if (cost < min) 

            min = cost; 

    

      

    // Возвращаем минимальное значение

    return min + fsum; 

  
// Основная функция, которая вычисляет
// минимальная стоимость бинарного дерева поиска.
// В основном он использует optCost () для поиска
// оптимальная стоимость.

int optimalSearchTree(int keys[], 

                      int freq[], int n) 

    // Здесь ключи массива [] предполагаются

    // отсортировано по возрастанию. Если ключи []

    // не сортируется, затем добавляем код для сортировки

    // ключи и переставляем freq [] соответственно.

    return optCost(freq, 0, n - 1); 

  
// Функция полезности для получения суммы
// элементы массива от freq [i] до freq [j]

int sum(int freq[], int i, int j) 

    int s = 0; 

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

    s += freq[k]; 

    return s; 

  
// Код драйвера

int main() 

    int keys[] = {10, 12, 20}; 

    int freq[] = {34, 8, 50}; 

    int n = sizeof(keys) / sizeof(keys[0]); 

    cout << "Cost of Optimal BST is " 

         << optimalSearchTree(keys, freq, n); 

    return 0; 

  
// Это код добавлен
// ратбхупендра

С

// Наивная рекурсивная реализация оптимального двоичного файла
// задача поиска дерева
#include <stdio.h>
#include <limits.h>

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j);

  
// Рекурсивная функция для расчета оптимальной стоимости
// двоичное дерево поиска

int optCost(int freq[], int i, int j)

{

   // Базовые случаи

   if (j < i)      // нет элементов в этом подмассиве

     return 0;

   if (j == i)     // один элемент в этом массиве

     return freq[i];

  

   // Получить сумму freq [i], freq [i + 1], ... freq [j]

   int fsum = sum(freq, i, j);

  

   // Инициализируем минимальное значение

   int min = INT_MAX;

  

   // Один за другим рассматриваем все элементы как корень и

   // рекурсивно находим стоимость BST, сравниваем

   // стоимость с min и обновление min при необходимости

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

   {

       int cost = optCost(freq, i, r-1) + 

                  optCost(freq, r+1, j);

       if (cost < min)

          min = cost;

   }

  

   // Возвращаем минимальное значение

   return min + fsum;

}

  
// Основная функция, которая вычисляет минимальную стоимость
// Двоичное дерево поиска. Он в основном использует optCost () для
// найти оптимальную стоимость.

int optimalSearchTree(int keys[], int freq[], int n)

{

     // Здесь ключи массива [] предполагаются отсортированными в

     // увеличение порядка. Если ключи [] не отсортированы, то

     // добавляем код для сортировки ключей и переставляем freq []

     // соответственно.

     return optCost(freq, 0, n-1);

}

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j)

{

    int s = 0;

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

       s += freq[k];

    return s;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int keys[] = {10, 12, 20};

    int freq[] = {34, 8, 50};

    int n = sizeof(keys)/sizeof(keys[0]);

    printf("Cost of Optimal BST is %d "

               optimalSearchTree(keys, freq, n));

    return 0;

}

Джава

// Наивная рекурсивная реализация оптимального двоичного файла
// задача поиска дерева

public class GFG 

{

    // Рекурсивная функция для расчета стоимости

        // оптимальное двоичное дерево поиска

    static int optCost(int freq[], int i, int j)

    {

       // Базовые случаи

       if (j < i)      // нет элементов в этом подмассиве

         return 0;

       if (j == i)     // один элемент в этом массиве

         return freq[i];

       

       // Получить сумму freq [i], freq [i + 1], ... freq [j]

       int fsum = sum(freq, i, j);

       

       // Инициализируем минимальное значение

       int min = Integer.MAX_VALUE;

       

       // Один за другим рассматриваем все элементы как корень и

           // рекурсивно находим стоимость BST, сравниваем

           // стоимость с min и обновление min при необходимости

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

       {

           int cost = optCost(freq, i, r-1) + 

                          optCost(freq, r+1, j);

           if (cost < min)

              min = cost;

       }

       

       // Возвращаем минимальное значение

       return min + fsum;

    }

      

    // Основная функция, которая вычисляет минимальную стоимость

        // Двоичное дерево поиска. Он в основном использует optCost () для

        // найти оптимальную стоимость.

    static int optimalSearchTree(int keys[], int freq[], int n)

    {

         // Здесь ключи массива [] предполагаются отсортированными в

             // увеличение порядка. Если ключи [] не отсортированы, то

             // добавляем код для сортировки ключей и переставляем freq []

             // соответственно.

         return optCost(freq, 0, n-1);

    }

      

    // Вспомогательная функция для получения суммы элементов массива

        // freq [i] to freq [j]

    static int sum(int freq[], int i, int j)

    {

        int s = 0;

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

           s += freq[k];

        return s;

    }

      

    // Код драйвера

    public static void main(String[] args) {

        int keys[] = {10, 12, 20};

        int freq[] = {34, 8, 50};

        int n = keys.length;

        System.out.println("Cost of Optimal BST is " +

                         optimalSearchTree(keys, freq, n));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Наивная рекурсивная реализация
# оптимальная задача бинарного дерева поиска

  
# Рекурсивная функция для расчета
# стоимость оптимального бинарного дерева поиска

def optCost(freq, i, j):

      

    # Базовые случаи

    if j < i:     # нет элементов в этом массиве

        return 0

    if j == i:     # один элемент в этом массиве

        return freq[i] 

      

    # Получить сумму freq [i], freq [i + 1], ... freq [j]

    fsum = Sum(freq, i, j) 

      

    # Инициализировать минимальное значение

    Min = 999999999999

      

    # Один за другим рассмотрим все элементы как

    # корень и рекурсивно найти стоимость

    # BST, сравните стоимость с мин.

    # и обновите мин при необходимости

    for r in range(i, j + 1):

        cost = (optCost(freq, i, r - 1) +

                optCost(freq, r + 1, j)) 

        if cost < Min

            Min = cost

      

    # Возврат минимального значения

    return Min + fsum

  
# Основная функция, которая рассчитывает минимум
# стоимость бинарного дерева поиска. Это в основном
# использует optCost (), чтобы найти оптимальную стоимость.

def optimalSearchTree(keys, freq, n):

      

    # Здесь ключи массива [] предполагаются

    # отсортировано по возрастанию. Если ключи []

    # не сортируется, затем добавьте код для сортировки

    # клавиш и переставить freq [] соответственно.

    return optCost(freq, 0, n - 1)

  
# Полезная функция для получения суммы
# элементы массива от freq [i] до freq [j]

def Sum(freq, i, j):

    s = 0

    for k in range(i, j + 1):

        s += freq[k] 

    return s

  
Код водителя

if __name__ == '__main__':

    keys = [10, 12, 20

    freq = [34, 8, 50

    n = len(keys) 

    print("Cost of Optimal BST is"

           optimalSearchTree(keys, freq, n))

      
# Этот код предоставлен PranchalK

C #

// Наивная рекурсивная реализация оптимального двоичного файла
// задача поиска дерева

using System;

  

class GFG

{

    // Рекурсивная функция для расчета стоимости

    // оптимальное двоичное дерево поиска

    static int optCost(int []freq, int i, int j)

    {

          

    // Базовые случаи

    // нет элементов в этом подмассиве

    if (j < i)     

        return 0;

      

    // один элемент в этом массиве

    if (j == i)     

        return freq[i];

      

    // Получить сумму freq [i], freq [i + 1], ... freq [j]

    int fsum = sum(freq, i, j);

      

    // Инициализируем минимальное значение

    int min = int.MaxValue;

      

    // Один за другим рассматриваем все элементы как корень и

    // рекурсивно находим стоимость BST, сравниваем

    // стоимость с min и обновление min при необходимости

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

    {

        int cost = optCost(freq, i, r-1) + 

                        optCost(freq, r+1, j);

        if (cost < min)

            min = cost;

    }

      

    // Возвращаем минимальное значение

    return min + fsum;

    }

      

    // Основная функция, которая вычисляет минимальную стоимость

    // Двоичное дерево поиска. Он в основном использует optCost () для

    // найти оптимальную стоимость.

    static int optimalSearchTree(int []keys, int []freq, int n)

    {

        // Здесь ключи массива [] предполагаются отсортированными в

        // увеличение порядка. Если ключи [] не отсортированы, то

        // добавляем код для сортировки ключей и переставляем freq []

        // соответственно.

        return optCost(freq, 0, n-1);

    }

      

    // Вспомогательная функция для получения суммы элементов массива

    // freq [i] to freq [j]

    static int sum(int []freq, int i, int j)

    {

        int s = 0;

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

        s += freq[k];

        return s;

    }

      

    // Код драйвера

    public static void Main() 

    {

        int []keys = {10, 12, 20};

        int []freq = {34, 8, 50};

        int n = keys.Length;

        Console.Write("Cost of Optimal BST is " +

                        optimalSearchTree(keys, freq, n));

    }

}

  
// Этот код предоставлен Sam007


Выход:

Cost of Optimal BST is 142

Временная сложность вышеуказанного наивного рекурсивного подхода является экспоненциальной. Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Мы можем видеть много повторяющихся подзадач в следующем дереве рекурсии для freq [1..4].

Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, оптимальная задача BST имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP), повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив cost [] [] снизу вверх.

Решение для динамического программирования
Ниже приводится реализация C / C ++ для оптимальной задачи BST с использованием динамического программирования. Мы используем вспомогательный массив cost [n] [n] для хранения решений подзадач. стоимость [0] [n-1] будет содержать окончательный результат. Сложность в реализации заключается в том, что сначала необходимо заполнить все диагональные значения, а затем значения, которые лежат на линии чуть выше диагонали. Другими словами, мы должны сначала заполнить все значения cost [i] [i], затем все значения cost [i] [i + 1], затем все значения cost [i] [i + 2]. Итак, как заполнить двумерный массив таким образом> Идея, использованная в реализации, аналогична задаче умножения цепочки матриц: мы используем переменную «L» для длины цепи и увеличиваем «L», одну за другой. Мы вычисляем номер столбца «j», используя значения «i» и «L».

C ++

// Код динамического программирования для оптимального двоичного поиска
// Проблема дерева
#include <bits/stdc++.h>

using namespace std;

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j); 

  
/ * Функция на основе динамического программирования, которая вычисляет
минимальная стоимость бинарного дерева поиска. * /

int optimalSearchTree(int keys[], int freq[], int n) 

    / * Создать вспомогательную 2D матрицу для хранения результатов

    подзадач * /

    int cost[n][n]; 

  

    / * стоимость [i] [j] = оптимальная стоимость бинарного дерева поиска

    который может быть сформирован из ключей [i] и [j].

    стоимость [0] [n-1] будет хранить результирующую стоимость * /

  

    // Для одного ключа стоимость равна частоте ключа

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

        cost[i][i] = freq[i]; 

  

    // Теперь нам нужно рассмотреть цепочки длиной 2, 3, ....

    // L - длина цепи.

    for (int L = 2; L <= n; L++) 

    

        // я номер строки в стоимости [] []

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

        

            // Получить номер столбца j из номера строки i и

            // длина цепи L

            int j = i+L-1; 

            cost[i][j] = INT_MAX; 

  

            // Попробуйте сделать все ключи в интервальных ключах [i..j] как root

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

            

            // c = стоимость, когда ключи [r] становятся корнем этого поддерева

            int c = ((r > i)? cost[i][r-1]:0) + 

                    ((r < j)? cost[r+1][j]:0) + 

                    sum(freq, i, j); 

            if (c < cost[i][j]) 

                cost[i][j] = c; 

            

        

    

    return cost[0][n-1]; 

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j) 

    int s = 0; 

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

    s += freq[k]; 

    return s; 

  
// Код драйвера

int main() 

    int keys[] = {10, 12, 20}; 

    int freq[] = {34, 8, 50}; 

    int n = sizeof(keys)/sizeof(keys[0]); 

    cout << "Cost of Optimal BST is " << optimalSearchTree(keys, freq, n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Код динамического программирования для оптимального двоичного поиска
// Проблема дерева
#include <stdio.h>
#include <limits.h>

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j);

  
/ * Функция на основе динамического программирования, которая вычисляет

  минимальная стоимость бинарного дерева поиска. * /

int optimalSearchTree(int keys[], int freq[], int n)

{

    / * Создать вспомогательную 2D матрицу для хранения результатов

      подзадач * /

    int cost[n][n];

  

    / * стоимость [i] [j] = оптимальная стоимость бинарного дерева поиска

       который может быть сформирован из ключей [i] и [j].

       стоимость [0] [n-1] будет хранить результирующую стоимость * /

  

    // Для одного ключа стоимость равна частоте ключа

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

        cost[i][i] = freq[i];

  

    // Теперь нам нужно рассмотреть цепочки длиной 2, 3, ....

    // L - длина цепи.

    for (int L=2; L<=n; L++)

    {

        // я номер строки в стоимости [] []

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

        {

            // Получить номер столбца j из номера строки i и

            // длина цепи L

            int j = i+L-1;

            cost[i][j] = INT_MAX;

  

            // Попробуйте сделать все ключи в интервальных ключах [i..j] как root

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

            {

               // c = стоимость, когда ключи [r] становятся корнем этого поддерева

               int c = ((r > i)? cost[i][r-1]:0) + 

                       ((r < j)? cost[r+1][j]:0) + 

                       sum(freq, i, j);

               if (c < cost[i][j])

                  cost[i][j] = c;

            }

        }

    }

    return cost[0][n-1];

}

  
// Вспомогательная функция для получения суммы элементов массива
// freq [i] to freq [j]

int sum(int freq[], int i, int j)

{

    int s = 0;

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

       s += freq[k];

    return s;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int keys[] = {10, 12, 20};

    int freq[] = {34, 8, 50};

    int n = sizeof(keys)/sizeof(keys[0]);

    printf("Cost of Optimal BST is %d "

                 optimalSearchTree(keys, freq, n));

    return 0;

}

Джава

// Динамическое программирование Java-кода для оптимального двоичного поиска
// Проблема дерева

public class Optimal_BST2 {

      

    / * Функция на основе динамического программирования, которая вычисляет

        минимальная стоимость бинарного дерева поиска. * /

    static int optimalSearchTree(int keys[], int freq[], int n) {

  

        / * Создать вспомогательную 2D матрицу для хранения результатов

           подзадачи * /

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

  

        / * cost [i] [j] = Оптимальная стоимость бинарного дерева поиска, которое

           может быть сформирован из клавиш [i] и клавиш [j]. Стоимость [0] [N-1]

           будет хранить результирующую стоимость * /

  

        // Для одного ключа стоимость равна частоте ключа

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

            cost[i][i] = freq[i];

  

        // Теперь нам нужно рассмотреть цепочки длиной 2, 3, ....

        // L - длина цепи.

        for (int L = 2; L <= n; L++) {

  

            // я номер строки в стоимости [] []

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

  

                // Получить номер столбца j из номера строки i и

                // длина цепи L

                int j = i + L - 1;

                cost[i][j] = Integer.MAX_VALUE;

  

                // Попробуйте сделать все ключи в интервальных ключах [i..j] как root

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

  

                    // c = стоимость, когда ключи [r] становятся корнем этого поддерева

                    int c = ((r > i) ? cost[i][r - 1] : 0)

                            + ((r < j) ? cost[r + 1][j] : 0) + sum(freq, i, j);

                    if (c < cost[i][j])

                        cost[i][j] = c;

                }

            }

        }

        return cost[0][n - 1];

    }

  

    // Вспомогательная функция для получения суммы элементов массива

    // freq [i] to freq [j]

    static int sum(int freq[], int i, int j) {

        int s = 0;

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

            if (k >= freq.length)

                continue;

            s += freq[k];

        }

        return s;

    }

  

    public static void main(String[] args) {

          

        int keys[] = { 10, 12, 20 };

        int freq[] = { 34, 8, 50 };

        int n = keys.length;

        System.out.println("Cost of Optimal BST is "

                + optimalSearchTree(keys, freq, n));

    }

  
}
// Этот код предоставлен Sumit Ghosh

python3

# Динамическое программирование кода для оптимального двоичного поиска
# Проблема дерева

  

INT_MAX = 2147483647

  
"" "Функция на основе динамического программирования, которая
вычисляет минимальную стоимость бинарного дерева поиска. «»»

def optimalSearchTree(keys, freq, n):

  

    "" "Создать вспомогательную 2D матрицу для хранения

        Результаты подзадач "" "

    cost = [[0 for x in range(n)] 

               for y in range(n)]

  

    "" "стоимость [i] [j] = оптимальная стоимость бинарного поиска

    дерево, которое может быть сформировано из ключей [i] к ключам [j].

    cost [0] [n-1] будет хранить результирующую стоимость "" "

  

    # Для одного ключа стоимость равна

    # частота ключа

    for i in range(n):

        cost[i][i] = freq[i] 

  

    # Теперь нам нужно рассмотреть цепочки

    # длина 2, 3, .... L - длина цепи.

    for L in range(2, n + 1):

      

        # я номер строки в стоимости

        for i in range(n - L + 2):

              

            # Получить номер столбца j из номера строки

            # я и длина цепи L

            j = i + L - 1

            if i >= n or j >= n:

                break

            cost[i][j] = INT_MAX

              

            # Попробуйте сделать все ключи в интервале

            # ключи [i..j] как root

            for r in range(i, j + 1):

                  

                # c = стоимость, когда ключи [r] становятся root

                # этого поддерева

                c = 0

                if (r > i):

                    c += cost[i][r - 1]

                if (r < j):

                    c += cost[r + 1][j]

                c += sum(freq, i, j) 

                if (c < cost[i][j]):

                    cost[i][j] = c

    return cost[0][n - 1

  

  
# Полезная функция для получения суммы
# элементы массива от freq [i] до freq [j]

def sum(freq, i, j):

  

    s = 0

    for k in range(i, j + 1):

        s += freq[k] 

    return

      
Код водителя

if __name__ == '__main__':

    keys = [10, 12, 20]

    freq = [34, 8, 50]

    n = len(keys)

    print("Cost of Optimal BST is",

           optimalSearchTree(keys, freq, n))

      
# Этот код предоставлен SHUBHAMSINGH10

C #

// Динамическое программирование кода C # для оптимального двоичного поиска
// Проблема дерева

using System;

  

class GFG

{

    / * Функция на основе динамического программирования, которая вычисляет

    минимальная стоимость бинарного дерева поиска. * /

    static int optimalSearchTree(int []keys, int []freq, int n) {

  

        / * Создать вспомогательную 2D матрицу для хранения результатов

        подзадачи * /

        int [,]cost = new int[n + 1,n + 1];

  

        / * cost [i] [j] = Оптимальная стоимость бинарного дерева поиска, которое

        может быть сформирован из клавиш [i] и клавиш [j]. Стоимость [0] [N-1]

        будет хранить результирующую стоимость * /

  

        // Для одного ключа стоимость равна частоте ключа

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

            cost[i,i] = freq[i];

  

        // Теперь нам нужно рассмотреть цепочки длиной 2, 3, ....

        // L - длина цепи.

        for (int L = 2; L <= n; L++) {

  

            // я номер строки в стоимости [] []

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

  

                // Получить номер столбца j из номера строки i и

                // длина цепи L

                int j = i + L - 1;

                cost[i,j] = int.MaxValue;

  

                // Попробуйте сделать все ключи в интервальных ключах [i..j] как root

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

  

                    // c = стоимость, когда ключи [r] становятся корнем этого поддерева

                    int c = ((r > i) ? cost[i,r - 1] : 0)

                            + ((r < j) ? cost[r + 1,j] : 0) + sum(freq, i, j);

                    if (c < cost[i,j])

                        cost[i,j] = c;

                }

            }

        }

        return cost[0,n - 1];

    }

  

    // Вспомогательная функция для получения суммы элементов массива

    // freq [i] to freq [j]

    static int sum(int []freq, int i, int j) {

        int s = 0;

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

            if (k >= freq.Length)

                continue;

            s += freq[k];

        }

        return s;

    }

  

    public static void Main() {

          

        int []keys = { 10, 12, 20 };

        int []freq = { 34, 8, 50 };

        int n = keys.Length;

        Console.Write("Cost of Optimal BST is "

                + optimalSearchTree(keys, freq, n));

    }

}
// Этот код предоставлен Sam007


Выход:

Cost of Optimal BST is 142

Примечания
1) Временная сложность вышеупомянутого решения O (n ^ 4). Временная сложность может быть легко уменьшена до O (n ^ 3) путем предварительного вычисления суммы частот вместо вызова sum () снова и снова.

2) В приведенных выше решениях мы рассчитали только оптимальную стоимость. Решения могут быть легко изменены, чтобы хранить структуру BST также. Мы можем создать еще один вспомогательный массив размером n для хранения структуры дерева. Все, что нам нужно сделать, это сохранить выбранный «r» во внутреннем цикле.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Оптимальное бинарное дерево поиска | DP-24

0.00 (0%) 0 votes