写在最前面
上题之前先写点前两天面试时面试官出的一道算法题的感想。他给的题目是实现一个栈，使得压栈、弹栈、求最小值的时间复杂度都是O(1)，讲出思路即可。听到这道题我第一个反应就是刷过，印象里多用一个双向队列实现，然后在开始思考具体怎么讲，结果感觉怎么讲都实现不了就有点绕进去了，最后也没讲清楚，其实应该额外使用一个栈来存储较小的值。而我刷过的那题，实际上是要实现一个O(1)插入、删除、返回最大值的队列。两道题相似，但是实现的数据结构完全不一样，所以前面写这一段希望读者刷LeetCode题千万不要习惯性思维，不要背题解，重要的是学习思考的思路和方法，也算是一点小教训吧。正片开始
题目
核心思路
这也是一道比较典型的DP问题，如果从1到3把图画出来的话，很容易发现 n 对应的二叉搜索树是与 n - 1 等之前的数有关的，至于什么关系，我们通过图来发现他。
可以看到图中蓝字的1，2，3表示n = 1, 2, 3时的二叉搜索树，红字及红框圈起来的是重复的结构，如蓝字2中重复了1的结构所以 n = 2 时的答案为 1 + 1 = 2; 蓝字3中重复了2和1中的结构，故 n = 3 时的答案为 2 + 2 + 1 = 5。这里的2 2 1分别是以1、3、2为根节点所得到的二叉树的数量。综上，我们可以根据此来定义DP数组的含义。
定义及初始化
int[] dp = new int[n + 1];//dp[i] 表示i个结点能排列的二叉搜索树的数量
根据此定义，我们很容易想到dp[0] = 0、dp[1] = 1。然后就需要寻找状态转移方程(递推公式)。
状态转移方程
根据核心思路的分析，我们需要将 n 个结点分别作为跟根节点，然后根据子节点个数就可以找到之前计算过的值进行复用。直接看上图观察，1和3对应的种类直接等于2，因为他们只有一棵子树，而2有两棵子树，他就要用 左子树的数 * 右子树的数(根据排列组合思想)，所以我们似乎可以得到这样的结论：
//i 及上文所说的 dp[i] 的下标
for(int j = 1; j <= i; j++){
//j作为根节点
if(j == 1 || j == i){
dp[i] += dp[j - 1] + dp[i - j];
}else{
dp[i] += dp[j - 1] * dp[i - j];
}
}
这样的结果便可以AC，不过可以发现if - else 部分之所以分支，是因为有 dp[0] = 0; 导致不得不把他分出去，但是他的值：0 + dp[i - j] (举例) 其实也可以变成 1 * dp[i - j] 只要我们令 dp[0] = 1 ，就可以把两个分支合并为一个，代码简洁了不少。
完整代码
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
//表示j作为根节点
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
虽然得到的结果很不错，但其实还有更简单的方法来解决。
卡特兰数(卡塔兰数)
这是个很神奇的数(或者说数列)，它跟斐波那契数列同样出名，更具体的内容还请自行百度。其实上边计算的 dp[i] 就等于第i个卡特兰数，至于其原因我也并没有深究，如果感兴趣可以找些资料深入研究。给出卡特兰数的递推公式：
其实他还有另一个化简后只与 n 相关的公式，但是要使用到组合数求阶乘，并不比递推简单高效，所以直接使用递推公式来实现即可(ps:虽然我想到了卡特兰数，但是实在想不起来公式了所以上来就用的DP来做题)
代码
class Solution {
public int numTrees(int n) {
long c = 1;
for(int i = 0; i < n; i++){
c = c * 2 * (2 * i + 1) / (i + 2);
}
return (int)c;
}
}
代码一下就简单了很多，复杂度也下降了一个级别降为O(N)，也许这就是数学的魅力吧。另外说一下使用long的原因，虽然最终结果是在int的范围内，但是在 c 除以 (i + 2) 之前其值是可能越界的(第19个卡特兰数为1767263190)，所以使用long来接收结果然后强转为int以防越界。如有不准确的地方还请指出，感谢相遇。
网友评论