力扣96题思路及题解
思路： 分析题意就是用n个值为1到n的节点创建二叉搜索树，求可以创建出不同二叉搜索树的种类，首先我们容易想到让每一个元素做根节点，求出其可以创建的不同二叉搜索树种类，然后对每种情况进行相加。确定根节点之后，在这种情况下可以创建多少种不同二叉树，要具体看其左子树有多少种，右子树有多少种，然后相乘就行。我们可以利用动态规划来解决，创建dp数组， dp[i]:表示连续的i个数能创建多少种二叉树 。那么对dp数组进行初始化，显然dp[1]=1,dp[2]=2,当i大于等于3的时候，我们就需要分不同元素做根节点，令j作为根节点则左子树有j-1个 右子树为i-j个，然后相乘再依次加到dp[i]里。经过分析我们会出现dp[0],注意一定要使dp[0]=1，不可以等于0因为做乘法运算。分析过程和代码详见下图。