动态规划最优二叉树搜索问题

### 动态规划求解最优二叉树搜索算法实现与解释

#### 定义问题
在构建最优二叉查找树时，目标是最小化平均查找成本。假设给定一组关键字`k1, k2,..., kn`以及对应的访问概率`p1, p2,..., pn`，还有失败节点（即不在集合中的键）的概率`q0,q1,...qn`。这里`qi`表示落在区间`(ki−1, ki)`内的查询比例。

#### 状态定义
设`C[i][j]`代表由第`i`到第`j`个关键词构成的最佳BST的成本；对于任意一对索引`i≤ j`，存在：

\[ C[i][j]=\min_{r=i}^{j}\left(\sum _{l=i}^{j}{P(l)}+\sum _{m=0}^{i-1}{Q(m)}+\sum _{n=j}^{N}{Q(n)}+C[i][r-1]+C[r+1][j]\right)\]

其中`P(l)`是成功匹配的关键字权重之和，而`Q(m)`则是未命中情况下的权值总和[^1]。

#### 初始化条件
当只有一个元素时，其作为根节点形成的子树成本等于自身的频率加上左侧外部路径上的虚结点频率:

\[ C[i][i]= P(i)+ Q(i-1), \quad i = 1,\ldots,n \]

边界情况下，如果不存在任何实际的数据项，则仅考虑两个虚拟叶子之间的开销:

\[ C[i][i-1]= Q(i-1), \quad i = 1,\ldots,n \]

#### 迭代计算过程
通过自底向上的方式填充表格，每次增加一个额外的层直到覆盖整个输入序列范围为止。具体来说就是先处理长度较短的连续片段再逐步扩展至更长的部分。

public static void OBST(double[] p, double[] q, int n){
    // Initialize cost table and root tracking array.
    double[][] c = new double[n + 1][n + 1];
    int[][] root = new int[n + 1][n + 1];

    for (int i = 0; i <= n; ++i) {
        c[i][i - 1] = q[i - 1]; // Boundary condition initialization
    }

    for (int l = 1; l <= n; ++l){ // Length of current segment being processed
        for (int i = 1; i <= n - l + 1; ++i){
            int j = i + l - 1;
            c[i][j] = Double.MAX_VALUE;

            for (int r = i; r <= j; ++r){
                double t = c[i][r - 1] + c[r + 1][j] + sum(p, q, i, j);
                if(t < c[i][j]){
                    c[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
}

private static double sum(double[] p, double[] q, int start, int end){
    double s = 0.0;
    for(int i=start;i<=end;++i)s+=p[i-1];
    for(int m=0;m<start-1;++m)s+=q[m];
    for(int n=end;n<p.length;++n)s+=q[n];
    return s;
}

此代码实现了上述描述的过程，并记录下了每个阶段所选最佳根的位置以便后续重建完整的结构图。