algorithm - 在求解最优二叉搜索树的同时添加频率总和

我指的是问题和解决方案。
首先，我不明白为什么在递归方程中加上频率之和。
有人能帮忙理解一下，举个例子可能是。
用作者的话说。
我们把i到j的频率之和相加（见上面的第一项
公式），因为每次搜索都要经过根和
每次搜索将进行一次比较
在代码中，频率之和（目的我不明白）对应于fsum。

int optCost(int freq[], int i, int j)
{
   // Base cases
   if (j < i)      // If there are no elements in this subarray
     return 0;
   if (j == i)     // If there is one element in this subarray
     return freq[i];

   // Get sum of freq[i], freq[i+1], ... freq[j]
   int fsum = sum(freq, i, j);

   // Initialize minimum value
   int min = INT_MAX;

   // One by one consider all elements as root and recursively find cost
   // of the BST, compare the cost with min and update min if needed
   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 minimum value
   return min + fsum;
}

其次，这种方法只会返回最优成本。关于如何得到实际的bst有什么建议吗？

最佳答案

为什么我们需要频率之和
频率之和背后的思想是正确计算特定树的成本。它的行为类似于累加器值来存储树的权重。
假设在第一级递归中，我们从位于树的第一级的所有键开始（我们还没有选择任何根元素）。记住权重函数-它是所有节点权重乘以节点级别的总和现在我们的树的权重等于所有键的权重之和，因为我们的任何键都可以位于任何级别（从第一个开始），无论如何，我们的结果中每个键至少有一个权重。
1）假设我们找到了最优的根键，比如keyr下一步，我们将除r之外的所有键向下移动一层，因为剩下的每个元素最多可以位于第二层（第一层已经被占用）因此，我们把每把钥匙的重量加在我们的总和上，因为不管怎样，对于所有的钥匙，我们至少有两倍的重量左键我们根据之前选择的r元素（从r向左和向右）分成两个子数组。
2）下一步是为第二级选择最佳键，从第一步剩下的两个子数组中各选择一个这样做之后，我们再次将所有关键点左移一层向下，并将它们的权重添加到和中，因为它们将至少位于第三层，因此我们将为每个关键点至少具有三倍的权重。
3）等等。
我希望这个解释能给你一些理解，为什么我们需要这个频率之和。
寻找最佳bst
正如作者在文章结尾提到的
2）在上述解中，我们只计算了最优成本。这个
解决方案也可以很容易地修改以存储bst的结构。
我们可以创建另一个大小为n的辅助数组来存储结构。
在树上我们要做的就是把选择的“r”存储在最里面
循环。
我们可以这么做下面你会发现我的实现。
关于它的一些注释：
1）由于我使用VisualC++，所以不支持非编译时常量表达式作为数组大小，所以我不得不用实用类“cc>”代替int[n][n]。
2）我使用了你在文章中提供的算法的第二个实现（带有记忆），因为添加功能来存储最佳的bst要容易得多。
3）作者代码有误：
第二个循环应该有Matrix作为上限而不是for (int i=0; i<=n-L+1; i++)。
4）我们存储最佳bst的方法如下：
对于每对n-L我们存储最佳密钥索引。这与最优成本相同，但我们不存储最优成本，而是存储最优密钥索引例如，对于n-L+1我们将拥有结果树根键i, j的索引。接下来，我们根据根元素索引0, n-1将数组分成两部分，并得到它们的最佳键索引我们可以通过访问矩阵元素r和r来实现这一点。等等实用程序函数“printResultTree”使用这种方法并按顺序打印结果树（左子树、节点、右子树）。所以你基本上得到了有序列表，因为它是二进制搜索树。
5）请不要因为我的代码而激怒我-我不是一个真正的C++程序员。:)

int optimalSearchTree(int keys[], int freq[], int n, Matrix& optimalKeyIndexes)
{
    /* Create an auxiliary 2D matrix to store results of subproblems */
    Matrix cost(n,n);
    optimalKeyIndexes = Matrix(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.SetCell(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; i++)
        {
            // Get column number j from row number i and chain length L
            int j = i + L - 1;
            cost.SetCell(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.GetCell(i, r - 1) : 0) +
                    ((r < j) ? cost.GetCell(r + 1, j) : 0) +
                    sum(freq, i, j);
                if (c < cost.GetCell(i, j))
                {
                    cost.SetCell(i, j, c);
                    optimalKeyIndexes.SetCell(i, j, r);
                }
            }
        }
    }
    return cost.GetCell(0, n - 1);
}

下面是实用程序类：

class Matrix
{
private:
    int rowCount;
    int columnCount;
    std::vector<int> cells;
public:
    Matrix()
    {

    }
    Matrix(int rows, int columns)
    {
        rowCount = rows;
        columnCount = columns;
        cells = std::vector<int>(rows * columns);
    }

    int GetCell(int rowNum, int columnNum)
    {
        return cells[columnNum + rowNum * columnCount];
    }

    void SetCell(int rowNum, int columnNum, int value)
    {
        cells[columnNum + rowNum * columnCount] = value;
    }
};

以及使用效用函数按顺序打印结果树的主要方法：

//Print result tree in in-order
void PrintResultTree(
    Matrix& optimalKeyIndexes,
    int startIndex,
    int endIndex,
    int* keys)
{
    if (startIndex == endIndex)
    {
        printf("%d\n", keys[startIndex]);
        return;
    }
    else if (startIndex > endIndex)
    {
        return;
    }

    int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
    PrintResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys);
    printf("%d\n", keys[currentOptimalKeyIndex]);
    PrintResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys);

}
int main(int argc, char* argv[])
{
    int keys[] = { 10, 12, 20 };
    int freq[] = { 34, 8, 50 };

    int n = sizeof(keys) / sizeof(keys[0]);
    Matrix optimalKeyIndexes;
    printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
    PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);

    return 0;
}

编辑：
下面可以找到创建简单树状结构的代码。
这里是实用程序类

struct TreeNode
{
public:
    int Key;
    TreeNode* Left;
    TreeNode* Right;
};

用0, r-1函数更新r+1, n-1函数

void BuildResultTree(Matrix& optimalKeyIndexes,
    int startIndex,
    int endIndex,
    int* keys,
    TreeNode*& tree)
{

    if (startIndex > endIndex)
    {
        return;
    }

    tree = new TreeNode();
    tree->Left = NULL;
    tree->Right = NULL;
    if (startIndex == endIndex)
    {
        tree->Key = keys[startIndex];
        return;
    }

    int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
    tree->Key = keys[currentOptimalKeyIndex];
    BuildResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys, tree->Left);
    BuildResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys, tree->Right);
}

int main(int argc, char* argv[])
{
    int keys[] = { 10, 12, 20 };
    int freq[] = { 34, 8, 50 };

    int n = sizeof(keys) / sizeof(keys[0]);
    Matrix optimalKeyIndexes;
    printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
    PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);
    TreeNode* tree = new TreeNode();
    BuildResultTree(optimalKeyIndexes, 0, n - 1, keys, tree);
    return 0;
}