首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

Unique Binary Search Trees解决办法

2013-10-30 
Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that st

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



class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> v(n+1, 0);
        v[0] = 1;
        v[1] = 1;
        v[2] = 2;
        if(n<=2)
           return v[n];
           
        for(int i=3; i<=n; i++)
            for(int j=1; j<=i; j++)
                v[i] += v[j-1]*v[i-j];
        return v[n];
    }
};
求人解释下这个Dp方程式的意义啊。。看不懂 Dp
[解决办法]
v[n] is total of n unique BST's

1 2 ... i ... n, we regard i as the root of tree, 1 ..2..(i-1) is left sub tree, (i+1) ..n is right sub tree.

so, v[n]=sum{v[i-1]*v[n-i]}, i=[1,n], v[0]=v[1]=1,

ex: Given n =3,
v[3]=sum{v[0]*v[2],v[1]*v[1],v[2]*v[0]} = 5
v[2]=sum{v[0]*v[1],v[1]*v[0]} =2

当我们取出一个数x作为根节点后,那么小于x的数必然会成为左子树,大于x的数必然会成为右子树,也就是说对于BST,只和数的个数有关

热点排行