## Unique Binary Search Trees

### 描述

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


### 分析

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


1             2
\          /
2      1


$f(2) = f(0) * f(1) \text{ , when 1 as root}$

$+ f(1) * f(0) \text{ , when 2 as root}$

$f(3) = f(0) * f(2) \text{ , when 1 as root}$

$+ f(1) * f(1) \text{ , when 2 as root}$

$+ f(2) * f(0) \text{ , when 3 as root}$

$f(i) = \sum_{k=1}^{i} f(k-1) \times f(i-k)$

### 代码

// Unique Binary Search Trees
// 时间复杂度O(n^2)，空间复杂度O(n)
public class Solution {
public int numTrees(int n) {
int[] f = new int[n + 1];

f[0] = 1;
f[1] = 1;
for (int i = 2; i