题目：

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

刚开始看到这道题，苦思冥想，愣了半天也没有半点思路TAT....于是google了一下这道题，才发现这题是比较经典的动态规划（Dynamic Programming）算法。由于之前没有接触过dp，所以特地停下刷题的脚步，google了大量dp算法的入门资料，具体学习过程将在“算法”栏目下另开一篇文章。

思路：
对于动态规划，我们其实只要找到这题的状态和状态转移方程，之后代码就很好写了。经过分析，不难发现：以 1 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 0 个元素的树， 右子树是 2 个元素的树。以 2 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 1 个元素的树，右子树也是 1 个元素的树。依此类推。 得到状态转移方程：f（i）就等于f(k−1)×f(i−k)的和。

代码：

public class Solution {    public int numTrees(int n)     {        int[] count=new int[n+1];                count[0]=1;        count[1]=1;        for(int i=2; i<=n; i++)        {            count[i]=0;            for(int j=1;j<=i;j++)            {                count[i]+=count[i-j]*count[j-1];            }        }                return count[n];    }}

本博客内容与代码均为作者Jarvis原创，如若转载请注明。

Unique Binary Search Trees