好吧，我希望有人可以向我解释一下。我正在为决赛做准备，但我还不太清楚。
问题是动态编程。构造最佳二叉搜索树(OBST)。我总体上了解动态编程，尤其是此问题的概念，但是我不了解此问题的递归形式。
我知道我们正在为这些节点的不断增加的子集构建最佳的二叉搜索树，并在进行操作时将答案保存在表中，以避免重新计算。我还知道，当您将树根植于a_ {k}时，从a_ {1}到a_ {k-1}的所有成功节点以及它们相应的虚拟不成功节点(即，树的叶子)都位于左子树，然后右子树中的子树是a_ {k + 1}至a_ {n}。
这是我不明白的方程式的递归形式:
c(i，j)=最小值(i
其中w(i，j)= q(i)+从i + 1到j的总和(q(l)+ p(l))。
因此，在c(i，j)中，从左到右，我们有左子树的代价+右子树的代价+成功搜索根的概率+ w(i，k-1)+ w(k + j)。
我的困惑是c(i，k-1)与w(i，k-1)有何不同。
文字是Horowitz，Sahni和Rajasekeran的《计算机算法》，但我也阅读过OBST上的CLRS并在线搜索，而我所遇到的任何事情都无法很好地解释方程式各部分之间的区别。
最佳答案
c(i，j)表示搜索包含关键字ki，...，kj的最佳二叉搜索树的预期成本。 w(i，j)表示包含 key ki，...，kj的子树的概率总和。对于公式:
c(i, j) = min (i < k <= j) {c(i, k-1) + c(k, j) + p(k) + w(i, k-1) + w(k,j)}
如果我们选择键k作为根，则c(i，k-1)+ w(i，k-1)表示左子树的成本。
c(k，j)+ w(k，j)表示右子树的成本。
p(k)表示根k的成本。
请注意:如果选择键k作为根，则左侧子树包含键ki，...，k(k-1)，右侧子树包含kyes
k(k + 1)，...，kj。但是我们不能简单地说:
c(i,j)=min (i < k <= j) {c(i, k-1) + c(k, j) + p(k)}
因为当我们为根选择 key k时，生成的子树的深度加了1。因此，c(i，k-1)+ w(i，k-1)将是左子树的正确代价!