# Unique Binary Search Trees

## Question

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


## 题解1 - 两重循环

### Python

class Solution:
# @paramn n: An integer
# @return: An integer
def numTrees(self, n):
if n < 0:
return -1

count = [0] * (n + 1)
count[0] = 1
for i in xrange(1, n + 1):
for j in xrange(i):
count[i] += count[j] * count[i - j - 1]

return count[n]


### C++

class Solution {
public:
/**
* @paramn n: An integer
* @return: An integer
*/
int numTrees(int n) {
if (n < 0) {
return -1;
}

vector<int> count(n + 1);
count[0] = 1;
for (int i = 1; i != n + 1; ++i) {
for (int j = 0; j != i; ++j) {
count[i] += count[j] * count[i - j - 1];
}
}

return count[n];
}
};


### Java

public class Solution {
/**
* @paramn n: An integer
* @return: An integer
*/
public int numTrees(int n) {
if (n < 0) {
return -1;
}

int[] count = new int[n + 1];
count[0] = 1;
for (int i = 1; i < n + 1; ++i) {
for (int j = 0; j < i; ++j) {
count[i] += count[j] * count[i - j - 1];
}
}

return count[n];
}
}


### 源码分析

1. 对 n 小于0特殊处理。
2. 初始化大小为 n + 1 的数组，初始值为0，但对 count[0] 赋值为1.
3. 两重 for 循环递推求得 count[i] 的值。
4. 返回 count[n] 的值。