最优二叉搜索树的重构动态方法

Question

总的来说，我对动态规划和 CS 的概念还很陌生。我通过阅读在线发布的讲座、观看视频和解决发布在 GeeksforGeeks 和 Hacker Rank 等网站上的问题来自学。

问题

给定输入

3 25 30 5

where 3 =  #of keys

25 = frequency of key 1

30 = frequency of key 2

5  = frequency of key 3

如果每个键都以优化的方式排列，我将打印成本最低的。这是一个最佳的二叉搜索树问题，我在 Geeks for Geeks 上找到了一个解决方案，它做了类似的事情。

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

// A utility function to get sum of array elements freq[i] to freq[j]
int sum(int freq[], int i, int j);

/* A Dynamic Programming based function that calculates minimum cost of
   a Binary Search Tree. */
int optimalSearchTree(int keys[], int freq[], int n)
{
    /* Create an auxiliary 2D matrix to store results of subproblems */
    int cost[n][n];

    /* cost[i][j] = Optimal cost of binary search tree that can be
       formed from keys[i] to keys[j].
       cost[0][n-1] will store the resultant cost */

    // For a single key, cost is equal to frequency of the key
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];

    // Now we need to consider chains of length 2, 3, ... .
    // L is chain length.
    for (int L=2; L<=n; L++)
    {
        // i is row number in cost[][]
        for (int i=0; i<=n-L+1; i++)
        {
            // Get column number j from row number i and chain length L
            int j = i+L-1;
            cost[i][j] = INT_MAX;

            // Try making all keys in interval keys[i..j] as root
            for (int r=i; r<=j; r++)
            {
               // c = cost when keys[r] becomes root of this subtree
               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];
}

// A utility function to get sum of array elements 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;
}

// Driver program to test above functions
int main()
{
    int keys[] = {0,1,2};
    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;
}

然而，在这个解决方案中，他们也接受了 "keys" 的输入，但他们似乎对最终答案没有影响，因为他们不应该。只有每个键被搜索多少次的频率才重要。

为了简单起见和理解这种动态方法，我想知道如何修改这个解决方案，以便它以上面显示的格式接受输入并打印结果。

Answer 1

您提供的函数确实有一个 keys 参数，但它没有使用它。您可以将其完全删除。

编辑：特别是，由于函数 optimalSearchTree() 根本不使用其 keys 参数，删除该参数只需要更改函数签名 (...

int optimalSearchTree(int freq[], int n)

...) 和该函数的一次调用。但是，由于您不需要此特定练习的密钥，因此您也可以将它们从主程序中完全删除，以便：

int main()
{
    int freq[] = {25, 30, 5};
    int n = sizeof(freq)/sizeof(freq[0]);
    printf("Cost of Optimal BST is %d ", optimalSearchTree(freq, n));
    return 0;
}

（将您指定的频率值替换为原始代码中的频率值）

但是，该函数确实假设频率是按调高的顺序给出的。它至少需要相对键顺序来完成它的工作，否则你无法构建 search 树。如果您对键值未知的想法感到不安，您可以将代码解释为使用 freq[] 数组中的索引作为键值的别名。这是可行的，因为上述假设的结果是 x -> keys[x] 是一个 1:1，order-preserving 从整数映射 0 ... n - 1 到实际的键是什么。

如果该函数不能假设频率最初是按键按递增顺序给出的，那么它可以先使用键将频率按该顺序排序，然后像现在一样继续。

最优二叉搜索树的重构动态方法

Refactoring Dynamic Approach for Optimal Binary Search Tree

c

algorithm

dynamic-programming