本文共 3437 字,大约阅读时间需要 11 分钟。
/************************************************
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
*******************************************************/
题目的意思是要求1…n共能组合成多少个二叉排序树。 下面是我参考的一位外国网友的解法,感谢他的分享。根据他的解释写出了如下的c++程序 The problem can be solved in a dynamic programming way. I’ll explain the intuition and formulas in the following.Given a sequence 1…n, to construct a Binary Search Tree (BST) out of the sequence, we could enumerate each number i in the sequence, and use the number as the root, naturally, the subsequence 1…(i-1) on its left side would lay on the left branch of the root, and similarly the right subsequence (i+1)…n lay on the right branch of the root. We then can construct the subtree from the subsequence recursively. Through the above approach, we could ensure that the BST that we construct are all unique, since they have unique roots.
The problem is to calculate the number of unique BST. To do so, we need to define two functions:
G(n): the number of unique BST for a sequence of length n.
G(n)
即使要求的二叉排序书的个数 F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
As one can see, G(n) is the actual function we need to calculate in order to solve the problem. And G(n) can be derived from F(i, n), which at the end, would recursively refer to G(n).
这里解释了可以将G(n)分解成一个个小问题,分别以1…n为根节的综合。First of all, given the above definitions, we can see that the total number of unique BST G(n), is the sum of BST F(i) using each number i as a root.
i.e.G(n) = F(1, n) + F(2, n) + ... + F(n, n).
G(0)=1, G(1)=1.
需要注意的地方,0具有1个二叉排序树
i.e.
F(i, n) = G(i-1) * G(n-i) 1 <= i <= n
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
下面是自己写的c++版本
int numTrees(int n) { vector cnts(n+1,0);//set all num is 0 cnts[0]=cnts[1]=1; //G(0)=G(1)=0 for (int i=2;i<=n;i++) for(int j=1;j<=n;j++) cnts[i]+=cnts[j-1]*cnts[i-j]; return cnts[n]; }
转载地址:http://vvdoi.baihongyu.com/