[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)，代码如下：

	class Solution {
	public:
	int numTrees(int n) {
	vector<int> dp(n + 1, 0);
	dp[0] = 1;
	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];
	}
	};

view raw Unique Binary Search Trees.cpp hosted with ❤ by GitHub

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