首页 > 代码库 > Unique Binary Search Trees

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

刚开始看到这道题,苦思冥想,愣了半天也没有半点思路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