Unique Binary Search Trees（dp）

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

BST树的定义：根节点左边所有节点的值小于根节点值，右边所有节点的值大于根节点的值，然后其左右子树又是BST

思路：例如序列：1,2,3,4,5

第一个数字的左边有0个数字，右边4个数字 dp[0]*dp[4]

第二个数字的左边有1个数字，右边3个数字 dp[1]*dp[3]

第三个数字的左边有2个数字，右边2个数字 dp[2]*dp[2]

第四个数字的左边有3个数字，右边1个数字 dp[3]*dp[1]

第五个数字的左边有4个数字，右边0个数字 dp[4]*dp[0]

所以我们要求的dp[5]就等于上面加起来的和，这里我们得假设dp[0]=1;

其实就是每个数字来当根节点，具体如下图所示

代码：

class Solution{

public:

    int numTrees(int n) {

        if(n<=) return n;

        vector<int> dp(n+,);

        dp[]=;

        for(int i=;i<=n;++i){

            int temp=;

            for (int j=;j<=i;++j)

            {

                temp+=dp[j-]*dp[i-j];

            }

            dp[i]=temp;

        }

        return dp[n];

    }

};

巴特西

Unique Binary Search Trees（dp）

最新文章

热门文章