UniqueBinarySearchTrees [source code]
public class UniqueBinarySearchTrees {
static
/******************************************************************************/
class Solution {
public int numTrees(int n) {
if (n <= 1)
return n;
// For convenience: when you say you have N numbers, I denote them 0-based as 0..N-1
// The table: first dimension is SIZE of a tree: 0..N
// second dimension is index, or 0-based value of the number: 0..N-1. +1 because want to use diagonal to store sumf or [..][I]
// entry itself is: number of unique trees of size I, and rooted with number (or index) J = 0..I-1
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1; // only 1 type of empty tree
dp[1][0] = 1; // only 1 type of size-1 tree
dp[1][1] = 1; // dp[i][i] (the diagonal) stores the sum of results for all [..][i]
for (int i = 2; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
// choose [J] of the all [I] numbers as root, then look left and right
int left_size = j - 1 + 1, right_size = (i - 1) - (j + 1) + 1;
dp[i][j] = dp[left_size][left_size] * dp[right_size][right_size];
dp[i][i] += dp[i][j];
}
}
return dp[n][n];
}
}
/******************************************************************************/
public static void main(String[] args) {
UniqueBinarySearchTrees.Solution tester = new UniqueBinarySearchTrees.Solution();
int[] inputs = {
1, 1,
2, 2,
3, 5,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int n = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.numTrees (n);
System.out.printf ("%d -> %s, expected: %d\n",
n, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
前面介绍过一次, 这种expand n(由简入繁)的题目, 给自己留一个心眼, 去思考一下reduce到比如n - 1的思路;
看给的例子来看, 好像这题还真的可以用这个方法?
DP的一个难点是设计表格, 包括entry和维度, 但是这个题目目前一点思路都没有, 所以这个直接设计表格的思路方向先搁置下来;
然后开始思考root level involvement. 一开始认为, 比如3的例子, 那么root就是数字3. 但是后来发现这个想法有问题, 你看他给的这个例子, 你如果盯着思考what do I do with 3, 会发现很难处理, 根本找不到规律, 尤其是第一个tree, 简直是捣乱的: 这算是什么?
后来重新思考到了这个root level involvement的定义(也就是subproblem, 因为root剥离之后剩下的就是subproblem), 就是what do you put at the root of a tree size n. 理解了这个之后, 有一个大概的思路;
画到右下角的时候, 大概能想到DP公式了;
最后稍微超时还是做出来了, 速度是0ms (7%). 回头看看, 几乎是认为做不出来了, 但是做完也还是觉得很有意思;
另外, 就算这个题目当时想到了subproblem structure, 其实表格设计本身也不是那么trivial:
一开始认为, 直接第一维是index, 然后第二维是size, 这样可以做到上图上半部分的表格结构; 但是开始要写的时候, 开始思考填表顺序, 因为我们习惯了用foreach row foreach col的顺序, 所以刚开始的这个定义我认为不太好; 所以改成了下面的这个定义; 然后就简单了;
一个小技巧就是, 在对角线位置(也就是index[size], which is not a legal position)存放当前[size]对应的row的所有结果的sum; 看到这里你也看出来了; 这个算法很容易优化空间到O(N): 只保留对角线就行了;
看上面的分段范围的计算的算是; 然后还有一个就是, 如果一个分段最后长度是0, 这个你是不能给0的, 因为最后要乘积, 所以我用了一个max保下限的技巧(不是min!!!), 来完成一个保证至少1的操作:
int left_size = Math.max (j - 1 + 1, 1), right_size = Math.max ((i - 1) - (j + 1) + 1, 1);
但是后来想到, 实际上根本就没有必要用这个操作: 你要保证的其实就是size等于0的时候返回1就是了(only 1 type of empty tree), 这样就可以保证乘积里面永远不会有0;
没有editorial;
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.
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).
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).
Particularly, the bottom cases, there is only one combination to construct a BST out of a sequence of length 1 (only a root) or 0 (empty tree).
i.e.G(0)=1, G(1)=1.
Given a sequence 1…n, we pick a number i out of the sequence as the root, then the number of unique BST with the specified root F(i), is the cartesian product of the number of BST for its left and right subtrees. For example, F(3, 7): the number of unique BST tree with number 3 as its root. To construct an unique BST out of the entire sequence [1, 2, 3, 4, 5, 6, 7] with 3 as the root, which is to say, we need to construct an unique BST out of its left subsequence [1, 2] and another BST out of the right subsequence [4, 5, 6, 7], and then combine them together (i.e. cartesian product). The tricky part is that we could consider the number of unique BST out of sequence [1,2] as G(2), and the number of of unique BST out of sequence [4, 5, 6, 7] as G(4). Therefore, F(3,7) = G(2) * G(4).i.e.
F(i, n) = G(i-1) * G(n-i) 1 <= i <= n
Combining the above two formulas, we obtain the recursive formula for G(n). i.e.G(n) = G(0) G(n-1) + G(1) G(n-2) + … + G(n-1) * G(0)
In terms of calculation, we need to start with the lower number, since the value of G(n) depends on the values of G(0) … G(n-1).With the above explanation and formulas, here is the implementation in Java.
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
他这个结果基本就是优化过空间的了; 不过核心的原理实际上还是和我差不多的;
First note that dp[k] represents the number of BST trees built from 1…k;
Then assume we have the number of the first 4 trees: dp[1] = 1 ,dp[2] =2 ,dp[3] = 5, dp[4] =14 , how do we get dp[5] based on these four numbers is the core problem here.
The essential process is: to build a tree, we need to pick a root node, then we need to know how many possible left sub trees and right sub trees can be held under that node, finally multiply them.
To build a tree contains {1,2,3,4,5}. First we pick 1 as root, for the left sub tree, there are none; for the right sub tree, we need count how many possible trees are there constructed from {2,3,4,5}, apparently it’s the same number as {1,2,3,4}. So the total number of trees under “1” picked as root is dp[0] dp[4] = 14. (assume dp[0] =1). Similarly, root 2 has dp[1]dp[3] = 5 trees. root 3 has dp[2]dp[2] = 4, root 4 has dp[3]dp[1]= 5 and root 5 has dp[0]*dp[4] = 14. Finally sum the up and it’s done.
Now, we may have a better understanding of the dp[k], which essentially represents the number of BST trees with k consecutive nodes. It is used as database when we need to know how many left sub trees are possible for k nodes when picking (k+1) as root.
public int numTrees(int n) {
int [] dp = new int[n+1];
dp[0]= 1;
dp[1] = 1;
for(int level = 2; level <=n; level++)
for(int root = 1; root<=level; root++)
dp[level] += dp[level-root]*dp[root-1];
return dp[n];
}
一样的;
另外, 我对我自己的想法的一个解释:
What makes it “fantastic”? Isn’t it just the same as the straight-forward solution that’s already the top-voted answer? Plus inconsistent spacing? You even both unnecessarily hardcode the dp[1] case instead of computing it (computing it would be shorter/purer and also prevent a crash for n=0).
他这么一说还是有点道理, 所以我也把我自己的代码优化了一下:
class Solution {
public int numTrees(int n) {
if (n == 0) return 0;
// For convenience: when you say you have N numbers, I denote them 0-based as 0..N-1
// The table: first dimension is SIZE of a tree: 0..N
// second dimension is index, or 0-based value of the number: 0..N-1. +1 because want to use diagonal to store sumf or [..][I]
// entry itself is: number of unique trees of size I, and rooted with number (or index) J = 0..I-1
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1; // only 1 type of empty tree
for (int i = 1; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
// choose [J] of the all [I] numbers as root, then look left and right
int left_size = j - 1 + 1, right_size = (i - 1) - (j + 1) + 1;
dp[i][j] = dp[left_size][left_size] * dp[right_size][right_size];
// dp[i][i] (the diagonal) stores the sum of results for all [..][i]
dp[i][i] += dp[i][j];
}
}
return dp[n][n];
}
}
这题好像居然有数学解法;
int numTrees(int n) {
// catalan树
// C(2n,n)/(n+1)
long long ans =1;
for(int i=n+1;i<=2*n;i++){
ans = ans*i/(i-n);
}
return ans/(n+1);
}
Simplified further:
int numTrees(int n) {
long long ans=1,i;
for(i=1;i<=n;i++)
ans = ans*(i+n)/i;
return ans/i;
}
这里有对这个问题的讲解: https://www.geeksforgeeks.org/program-nth-catalan-number/
Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.
- Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
- Count the number of possible Binary Search Trees with n keys (See this)
- Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
上面那个O(N)实现是借用了这个: https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/ O(N)时间找组合数;
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]
Also, C(n, k) = C(n, n-k) // we can change r to n-r if r > n-r
好像其实并没有什么神秘的; 不过说实话我不太喜欢他们上面这个乘浮点数的操作; 我写的话, 就两pass; 不对, 如果先把分子全乘了再除分母, 那么可能会有overflow, 好像也不好解决;
另外, 这里是MIT的一个作业, 是大量的对于catalan数字的应用的分析;
看geeks4geeks那个帖子里面, 首先这题证明是catalan并不难, catalan的定义完全就是我们这题的这个recursive formula; 问题是C(2n, n) / (n + 1)这个用来计算catalan的formula, geeks4geeks实际上也没有给出证明;
难点好像就是对于这个formula的证明了, 在Wiki里面翻到了; 很复杂, 不贴在这里了;
submission基本就是这么一回事了;
Problem Description
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
Difficulty:Medium
Total Accepted:143.2K
Total Submissions:342.7K
Contributor:LeetCode
Companies
snapchat
Related Topics
dynamic programmingtree
Similar Questions
Unique Binary Search Trees II