4

给定 n，有多少个结构唯一的 BST（二叉搜索树）存储值 1...n？

例如，给定 n = 3，总共有 5 个唯一的 BST。

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

我有这个解决方案：

/**
 * Solution:
 * DP
 * a BST can be destruct to root, left subtree and right subtree.
 * if the root is fixed, every combination of unique left/right subtrees forms
 * a unique BST.
 * Let a[n] = number of unique BST's given values 1..n, then
 * a[n] = a[0] * a[n-1]     // put 1 at root, 2...n right
 *      + a[1] * a[n-2]     // put 2 at root, 1 left, 3...n right
 *      + ...
 *      + a[n-1] * a[0]     // put n at root, 1...n-1 left
 */
int numTrees(int n) {
    if (n < 0) return 0;
    vector<int> trees(n+1, 0);
    trees[0] = 1;

    for(int i = 1; i <= n; i++) 
        for (int j = 0; j < i; j++) 
            trees[i] += trees[j] * trees[i-j-1];

    return trees[n];
}

因为这个答案是很久以前给出的，无法触及这个'dragonmigo'家伙。该解决方案被接受，我的问题是：

在评论中， trees[0] 指的是案例1。(0+1 = 1)

如果是这样，则 trees[n-1] 应该引用案例1...n而不是案例2...n。(n-1+1=n)

我的想法错了吗？

ps 我知道这实际上是一个加泰罗尼亚数字，并且我知道使用演绎公式解决它的算法。

4

1 回答 1

9

trees[n]是恰好具有n节点的树的数量。有 1 棵树有 0 个节点，因此 trees[0] == 1. 对于给定n > 0，有一个根节点和两个子树，其总大小为：n-1

  • trees[n-1]左边和trees[0]右边可能的树
  • trees[n-2]左边和trees[1]右边可能的树
  • ...
  • trees[1]左边和trees[n-1-1]右边可能的树
  • trees[0]左边和trees[n-1]右边可能的树

当您trees[k]在左侧和trees[l]右侧有可能的树时，它就可以trees[k]*trees[l]进行组合。这表示：

trees[n] = trees[n-1]*trees[0]
         + trees[n-2]*trees[1]
         + ...
         + trees[1]*trees[n-2]
         + trees[0]*trees[n-1]

外循环计算 all trees[n]。内部循环使用上面显示的分解（以及之前所有值的计算）来计算每一个n。

于 2014-07-15T13:35:13.097 回答