[leetcode]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.

题目解析

我们可以发现,只需求出左、右子树各有多少种,二者相乘即为以 i 作为root时BST的总数。所以我们可以用动态规划来实现。当节点数为0个的时候,子树为0个,节点为1个的时候,子树为1个,节点数为2个的时候,子树为2个。当n>=3的时候,左右子树种类之积就是结果。所以我们只需要由下至上求解即可。

代码实现

    int numTrees(int n) {
        vector<int>num;
        num.push_back(1);
        for(int i=1; i<=n; i++)
        {
            num.push_back(0);
            if(i<3)
            {
                num[i]=i;
            }
            else{
                for(int j=1;j<=i;j++)
                {
                    num[i]+=num[j-1]*num[i-j];
                }
            }

        }
        return num[n];
    }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注