## Description

Unique Binary Search Trees

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

Example:

Input: 3

Output: 5

Explanation: 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


## Solution

n = 3为例，有数字1、2、3；设解为F(3)=f(1~3)

F(3)分解：

1. 如果以1root结点，则右边2~3F(2)=f(2~3)个解
2. 如果以2root，则左边有F(1)=f(1~1)、右边有F(1)=f(3~3)；总F(1)*F(1)
3. 如果以3root，则左边有F(2)=f(1~2)

$$F(n) = \sum_{i=0}^{n}F(i) * F(n-i-1) ; F(0) = 1;$$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  class Solution { public: int numTrees(int n) { int *dp = new int[n+1]{1, 1}; // {F(0), F(1)} for (int i = 2; i <= n; ++i) { dp[i] = 0; for (int k = 0; k < i; ++k) { dp[i] += (dp[k] * dp[i - k - 1]); } } int r = dp[n]; delete []dp; return r; } };