编程用动态规划的自底向上的方法实现最优二叉查找树算法

动态规划的自底向上的方法实现最优二叉查找树算法的步骤如下：

1. 初始化辅助数组d、w、root，其中d[i][j]表示从i到j的最小搜索代价，w[i][j]表示从i到j的权值和，root[i][j]表示从i到j的最小搜索代价对应的根结点。

2. 对于所有单个结点i = j，d[i][j] = w[i][j]，根据定义，w[i][j]表示从i到j的权值和。

3. 对于所有区间长度大于1的子区间[i, j]，计算d[i][j]和root[i][j]。

a) 初始化d[i][j]为一个很大的数，root[i][j]为空。

b) 枚举根结点k(i ≤ k ≤ j)，计算左右子树的最小搜索代价和权值和。

i) 左子树为[i, k-1]，右子树为[k+1, j]。

ii) 左子树的搜索代价为d[i][k-1]，权值和为w[i][k-1]，右子树的搜索代价为d[k+1][j]，权值和为w[k+1][j]。

iii) 总搜索代价为其根结点k的权值w[i][j]加上左右子树的最小搜索代价之和。

iv) 更新d[i][j]和root[i][j]。

4. 最终的最小搜索代价为d[1][n]，其中n为结点总数。

同时，此问题的详细解题过程可参考一些经典的算法教材，如《算法导论》等。