(LeetCode 动态规划（基础版）)96. 不同的二叉搜索树 （递推 || 递归）

题目：96. 不同的二叉搜索树

思路：二叉树长度为n时，枚举每个点u作为根节点root，那么root左边的数构成左子树种数left，root右边的数构成右子树种数right，那么当前u为根节点下，二叉树的种数为left*right。答案便是总和，时间复杂度0(n^2)。

方法一：递推，时间复杂度0(n^2)。

C++版本：

class Solution {
public:int numTrees(int n) {vector<int> f(n+1);f[0]=1;for(int len=1;len<=n;len++){for(int root=1;root<=len;root++){f[len]+=f[root-1]*f[len-root];}}return f[n];}
};

JAVA版本：

class Solution {public int numTrees(int n) {int[] f=new int[n+1];f[0]=1;for(int len=1;len<=n;len++){for(int root=1;root<=len;root++){f[len]+=f[root-1]*f[len-root];}}return f[n];}
}

Go版本：

func numTrees(n int) int {f:=make([]int,n+1)f[0]=1for len:=1;len<=n;len++ {for  root:=1;root<=len;root++ {f[len]+=f[root-1]*f[len-root]}}return f[n]
}

方法二：递归，深度优先搜索dfs，时间复杂度0(n^2)。

C++版本：

class Solution {
public:int dfs(int st,int ed,vector<int> &f){if(st>ed) return 1;if(f[ed-st+1]!=-1) return f[ed-st+1];int sum=0;for(int i=st;i<=ed;i++){sum+=dfs(st,i-1,f)*dfs(i+1,ed,f);}return f[ed-st+1]=sum;}int numTrees(int n) {vector<int> f(n+1,-1);f[0]=1;dfs(1,n,f);return f[n];}
};

JAVA版本：

class Solution {int dfs(int st,int ed,int[] f){if(st>ed) return 1;if(f[ed-st+1]!=-1) return f[ed-st+1];int sum=0;for(int i=st;i<=ed;i++){sum+=dfs(st,i-1,f)*dfs(i+1,ed,f);}return f[ed-st+1]=sum;}public int numTrees(int n) {int[] f=new int[n+1];Arrays.fill(f,-1);f[0]=1;return dfs(1,n,f);}
}

Go版本：

func numTrees(n int) int {f:=make([]int,n+1)var dfs func(int,int) int dfs =func(st int,ed int) int{if st>ed {return 1}if f[ed-st+1]!=0  {return f[ed-st+1]}sum:=0for i:=st;i<=ed;i++ {sum+=dfs(st,i-1)*dfs(i+1,ed)}f[ed-st+1]=sumreturn sum}dfs(1,n)return f[n]
}