LeetCode：独特的二进制搜索树计算(LeetCode: Unique Binary Search Trees Calculation)

 给定n，存储值1 ... n的结构唯一BST（二叉搜索树）有多少？ 
 
 例如，给定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我知道这实际上是一个加泰罗尼亚号码，我知道使用演绎公式来解决它的算法。 

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
 
For example, Given n = 3, there are a total of 5 unique BST's.
 
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
 
I've got this solution:
 
/**
 * 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];
} 
 
Because this answer was given out too long ago to touch this 'dragonmigo' guy. This solution is accepted and my problem is:
 
In the comment, trees[0] refers to case 1. (0+1 = 1)
 
If so, trees[n-1] should refer to case 1...n rather than the case 2...n. (n-1+1=n)
 
Is my thinking wrong?
 
p.s. I know this is actually a Catalan number and I know the algorithm using the deduction formula to solve it.

原文：https://stackoverflow.com/questions/24755059