Unique Binary Search Trees

Unique Binary Search Trees

Description:

Given n, how many structurally unique BSTs (binary search trees) that store values 1…n?

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

分析：

没想出来怎么做，暂时参考别人的，这里先做个记录。

参考：

喜刷刷: [LeetCode] Unique Binary Search Trees I, II

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
        // write your code here
        vector<int> nums(n + 1, 0);
        nums[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                nums[i] += nums[j] * nums[i-1-j];
            }
        }
        
        return nums[n];
    }
};