继续打卡算法题，今天学习的是LeetCode第96题不同的二叉搜索树，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
本题是给一个数n，求这个数可以组成不同的二叉树，由于二叉搜索树的特性，左子树小于根节点，右子树大于根节点。
那么组成的二叉树总数是分别是由 1到n为根节点可以组成的二叉树的总数。
比如n=3,分别需要求：
根为1可以组成的二叉树
根为2可以组成的二叉树
根为3可以组成的二叉树
而求根为i可以组成的二叉树数目，它等于i-1 和 n-i个节点可以组成的树数目之积。 我们可以得到递推公式：
dp[n] + = dp[i-1] * dp[j-i]
本题解题技巧
1、根据二叉树特性，推导递推公式
编码解决
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
//求数字i可以组成dp[i]个二叉树
for(int i=2; i<=n; i++) {
//求以j为根，可以组成多少二叉树
for(int j=1; j<=i; j++) {
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}
总结
1、本题属于动态规划题目，需要理解递推公式推演的脉络。
