96. 不同的二叉搜索树
解法:我们先举个例子，如果固定
3
3
3 作为根节点，左子树节点就是
{
1
,
2
}
{1,2}
{1,2} 的组合，右子树就是
{
4
,
5
}
{4,5}
{4,5} 的组合。左子树的组合数和右子树的组合数乘积就是
3
3
3 作为根节点时的 BST 个数
那么接下来的代码就很好写了，按照递归的思路，每次闭区间
[
l
o
,
h
i
]
[lo, hi]
[lo,hi] 的数字能组成
c
o
u
n
t
(
l
o
,
h
i
)
count(lo, hi)
count(lo,hi) 种 BST就能知道
[
1
,
n
]
[1, n]
[1,n] 有多少中 BST
按照动态规划的思路，我们可以增加一个叫做 m e m o memo memo 的二维数组来帮助我们消除重叠的子问题
但是在代码中还有一个细节要注意，当 l o > h i lo > hi lo>hi，闭区间 [ l o , h i ] [lo, hi] [lo,hi] 肯定是个空区间，为什么要返回 1 1 1 呢？
我们思考一下一个闭区间 [ l o , h i ] [lo, hi] [lo,hi] 到底定义了什么， [ 1 , 1 ] [1, 1] [1,1] 定义了当前树中只有一个结点，那么只有唯一的一种情况， [ 1 , 2 ] [1, 2] [1,2] 定义了以 1 1 1 为根结点和以 2 2 2 为根结点的 BST
那么什么时候会出现空区间的情况呢， i = 1 i = 1 i=1 时，以 1 1 1 为根结点，左子树是 c o u n t ( 1 , 0 ) count(1, 0) count(1,0)，右子树是 c o u n t ( 2 , 2 ) count(2, 2) count(2,2)，此时对应的就是根结点左孩子为空，右孩子为 2 2 2，那么是一种合理的 BST
所以，空区间并不代表什么也没有，而是对应着一个空节点 null，虽然是空节点，但是也是一种情况，所以要返回 1 1 1 而不能返回 0 0 0
如果你任然不是十分清楚这一步的原理， 可以参看以下 LeetCode 95. 不同的二叉搜索树 II，在构造树的过程中你将更加明白为什么返回是 1 1 1
class Solution {
public:
int numTrees(int n) {
vector> memo(n + 1, vector(n + 1, 0));
return count(1, n, memo);
}
int count(int lo, int hi, vector>& memo){
if (lo > hi) return 1;
if (memo[lo][hi] != 0) return memo[lo][hi];
int res = 0;
for (int i = lo; i <= hi; i++)
{
int left = count(lo, i - 1, memo);
int right = count(i + 1, hi, memo);
res += left * right;
}
memo[lo][hi] = res;
return res;
}
};
