LeetCode:唯一二进制搜索树计算

Question

给定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'的家伙.这个解决方案被接受,我的问题是:

在注释中,树[0]指的是案例1.(0 + 1 = 1)

如果是这样,树[n-1]应该参考情况1 ... n而不是情况2 ... n.第(n-1 + 1 = n)的

我的想法错了吗？

ps我知道这实际上是一个加泰罗尼亚数字,我知道算法使用演绎公式来解决它.

Answer 1

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]

外循环计算所有trees[n].内循环使用上面显示的分解(以及之前所有值的计算)计算这些中的每一个n.