博文中会简要介绍Leetcode P0096题目分析及解题思路。
“Unique Binary Search Trees”是p0095的原型题，这道题同样有两种主流解法，一种是递归（回溯法），第二种是动态规划。参考p0095的思路，按照递归的解法写出递推表达式，不难发现是在求Catalan Number，而有了递推表达式，动态规划也就很容易实现。
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
结合p0095的递归解法，思路如下：
令G(n)是长度为n的序列能产生的不同二叉搜索树个数；
令F(i, n)是以i为根结点，长度为n的序列能产生的不同二叉搜索数个数；
可知，
G(n) = F(1, n)+F(2, n)+F(3, n)+...+F(n-1, n)+F(n, n)
而我们观察F(i, n)可以知道，如果我们以i为根结点，那么左子树由序列1...i-1组成，右子树有序列i+1...n组成。而不同左子树的个数则是G(i-1)，不同右子树的个数实际就是G(n-i)。那么可以得到，
F(i, n) = G(i-1)*G(n-i)
那么将这个等式代入最初的G(n)的式子，我们可以得到，
G(n) = G(0)*G(n-1)+G(1)*G(n-2)+G(2)*G(n-3)+...+G(n-2)*G(1)+G(n-1)*G(0)
实际上，这个就是最终的递推式。
以下是Java的题解代码实现。
class Solution {
public int numTrees(int n) {
if (n == 0)
return 0;
int[] dp = new int[n+1];
dp[0] = 1;
// Catalan Number
for (int i1=1; i1<=n; ++i1) {
for (int j2=0; j2<=i1-1; ++j2)
dp[i1] += dp[j2]*dp[i1-j2-1];
}
return dp[n];
}
}
以下是C++的题解代码实现。
class Solution {
public:
int numTrees(int n) {
if (n == 0)
return 0;
int *dp = new int[n+1];
dp[0] = 1;
// Catalan Number
for (int i1=1; i1<=n; ++i1) {
dp[i1] = 0;
for (int j2=0; j2<=i1-1; ++j2)
dp[i1] += dp[j2]*dp[i1-j2-1];
}
return dp[n];
}
};