96.Unique Binary Search Trees¶
Tags: Medium
Dynamic Programming
Tree
Links: https://leetcode.com/problems/unique-binary-search-trees/
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
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) {
vector<int> dp(n + 1);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
}
};
最开始并没有往卡特兰数的方向去想,最初的想法是利用分治法,也就是利用二叉树的性质,右子树的所有节点数值必然大于根节点,左子树节点数值必然小于根节点,那么对于当前结果,其值等于左子树能排列的个数和右子树能排列的个数相乘,特殊情况,左子树或右子树为空,视为种类为1.不同的数值依次作为根节点,所以可以写出最原始的方法。
int numTrees(int n) {
if (n <= 1) return 1;
int res = 0;
for (int i = 1; i <= n; ++i) {
res += numTrees(i-1)*numTrees(n-i);
}
return res;
}
分析这个程序,发现会有很多重复计算,很类似斐波那契数列,所以考虑用一个数组来存储已经计算过的结果,就避免了重复计算。
对于1到n这些数,取i
作为根,则i
的左子树有i-1
个数,右子树有n-i
个数,如果增加一个数组dp
来存储,则dp[0] = dp[1] = 1
,然后内层循环要从j = 0
开始。
细节方面不需要考虑dp[i] += dp[j] * dp[i - j - 1];
的溢出问题,因为题目给出的返回类型是int
,所以能保证不会溢出,如果数据很大的时候,比如对于10^9+7取模。
卡特兰数之前总结过,原始的数学模型:
n个1和n个-1构成的2n项: $$ a_{1}, a_{2}, \cdots, a_{2 n} $$ 其部分和满足: $$ a_{1}+a_{2}+\cdots+a_{k} \geqslant 0, \quad(k=1,2, \cdots, 2 n) $$ 的数列的个数等于第n个Catalan数: $$ C_{n}=\frac{1}{n+1}\left(\begin{array}{l}{2 n} \ {n}\end{array}\right) \quad(n \geqslant 0) $$ 其实恰好和这个序列保持一致。
第二种方法就是根据公式来写,相当于把求解公式展开:
class Solution {
public:
int numTrees(int n) {
long long res = 1;
for (int i = n + 1; i <= 2 * n; ++i) {
res = res * i / (i - n);
}
return res / (n + 1);
}
};
做数学类的计算的时候,尤其要注意的是数据类型,第六行的res = res * i / (i - n);
写成res *= i / (i - n)
就会出错,是因为i / (i -n)
会自动取整,比如n=3
的时候循环里面做下面的计算
$$
\frac{4}{1} \times \frac{5}{2} \times \frac{6}{3}
$$
计算5 / 2 = 2
. 则最后结果为4.