[LeetCode]Unique Binary Search Trees

也是递归思路用DP 优化的题。用DP[i]表示用1- i的数可以组成的unique binary search tree，那么我们有递推公式：

• DP[i] = sum(DP[k] * DP[i - 1 - k]), where 0 <= k <= i - 1

对于1到i的i个数而言，我们分别计算每一个数作为根的时候所能构成的unique binary search tree，对于以k + 1为根的数，其左子树只能从1到k, 右子树只能从k + 2到i。那么左右子树分别有DP[k]和DP[i - 1 - k种可能，我们把这些可能相乘。将所有以k为根的结果相加就是我们从1-i的结果数。这就是递推方程的含义。

代码根据递推方程写即可，空间复杂度O(n^2)，空间复杂度 O(n)，代码如下：

另外值得一提的是Unique Binary Search Tree的数量是Catalan Number，有O(n)时间计算的公式，但是这里我们就不细讲了，感兴趣的可以google。