给定一个已排序的搜索键数组 keys[0.. n-1] 和一个频率计数数组 freq[0.. n-1]，其中 freq[i] 表示对 keys[i] 的搜索次数。我们需要构建一个包含所有键的二叉搜索树，使得所有搜索的总成本尽可能小。
BST 节点的成本定义为该节点的层级乘以其频率。根节点的层级为 1。
示例：
> 输入： keys[] = [10, 12], freq[]= [34, 50]
> 输出： 118
> 解释： 可能存在以下两种 BST
> 树 I 的成本为 341 + 502 = 134
> 树 II 的成本为 501 + 342 = 118
> 输入： keys[] = [10, 12, 20], freq[]= [34, 8, 50]
> 输出： 142
> 解释： 可能存在多种 BST。在所有可能的 BST 中，第五棵 BST 的成本为 150 + 234 + 3*8 = 142，这是最小的。
> !Optimal-Binary-Search-Tree-2
目录
- [朴素方法] 使用 递归 – O(2^n) 时间和 O(n) 空间
- [期望方法 1] 自顶向下动态规划 (记忆化) – O(n^3) 时间和 O(n^2) 空间
- [期望方法 2] 自底向上动态规划 (制表) – O(n^3) 时间和 O(n^2) 空间
直觉：
我们本可以将每个频率乘以其所在的树层级，但跟踪层级变化会使解决方案变得非常复杂。
> 取而代之的是，我们使用一种更巧妙的方法。每当我们选择一个节点作为根节点时，我们就加上从起始索引到结束索引 之间所有节点的频率总和。选择了根节点之后，该组中的每个节点（包括左右子树）都会自动向下一层移动。当递归继续深入并解决较小的子树时，它们的频率总和会被再次自动加上，这与将每个节点乘以其层级的效果完全一致。
[朴素方法] 使用 递归 – O(2^n) 时间和 O(n) 空间
> 正如我们在直觉部分讨论的那样，我们尝试将每个键都作为树的根。对于每一种根的选择，我们递归地计算其左右子树的代价。在每一步中，我们都加上该范围内频率的总和，以考虑到所有键都向下移动了一层。我们对所有可能的根重复此过程，并最终选择给出最小总成本的配置。
C++
CODEBLOCK_c12951fe
Java
//Driver Code Starts
import java.util.Arrays;
public class GFG {
//Driver Code Ends
// function to get sum of
// array elements 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;
}
// A recursive function to calculate
// cost of optimal binary search tree
static int optCost(int[] freq, int i, int j) {
// no elements in this subarray
if (j < i)
return 0;
// one element in this subarray
if (j == i)
return freq[i];
// Get sum of freq[i], freq[i+1], … freq[j]
int fsum = sum(freq, i, j);
int minCost = Integer.MAX_VALUE;
// One by one consider all elements
// as root and recursively find cost
// of the BST
for (int r = i; r <= j; r++) {
int cost = optCost(freq, i, r – 1) + optCost(freq, r + 1, j);
if (cost < minCost)