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 <= n; ++i) {            for (int k = 1; k <= i; ++k)                f[i] += f[k-1] * f[i - k];        }        return f[n];    }}