[二叉搜索树][动态规划]leetcode96：不同的二叉搜索树(medium)

动态规划]leetcode96：不同的二叉搜索树(medium)"/>

[二叉搜索树][动态规划]leetcode96：不同的二叉搜索树(medium)

题目：

代码如下：

• 卡特兰数
  

代码如下：

class Solution {
public://题解：带备忘录的动态规划//G(n)表示n个节点在二叉搜索树中的个数G(n)=f(1)+f(2)+...+f(n)//f(n)表示以i为根的二叉搜索树个数，f(i)=G(i-1)*G(n-i)，左子树i-1个节点，右子树n-i个节点，然后左右子树对应的二叉搜索树相乘//卡特兰数：dp[i]=dp[0]*dp[i-1]+dp[1]*dp[i-2]+...+dp[i-1]*dp[0]int numTrees(int n) {vector<int> dp(n+1,0);dp[0]=1;for(int i=1;i<=n;++i){for(int j=1;j<=i;++j){//j的范围[0,i-1]，(i-j)的范围[i-1,0]，对应上面的卡特兰数dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
};