#if 0
class Solution {
public:
int numTrees(int n) {
vector<int> s(n+1); // 取值范围有n个数，取n个数范围内的任意一个树做根节点的二叉搜索树的种数的和
/** 那么对于任意数 i 做 根节点，那么 i 的左侧 有i-1个数，这么多数会有s[i-1] 种二叉树，右侧有 j-i 个数，有s[j-i]种二叉树的排列方式，
将两者相乘，然后累加不同取值i时的情况，就得到递推公式
** 有递推公式 S[j] = 累加{sum[i-1] * sum[j-i]} ,1<=i<=j , 1<=j<=n i 为不同的根节点的取值，j 为数的多少
**/
//初始化数组
s[0] = 1; //表示没有数据时的二叉树的种数，很显然，这也属于一种情况，只有一个数的二叉树的种数为1.
s[1] = 1;
for(int j = 2; j <=n ; j++){
for(int i = 1; i <= j;i++){
s[j] +=s[i-1] * s[j-i];
}
}
return s[n];
}
};
#endif
#if 0
class Solution {
public:
int numTrees(int n) {
vector<vector<int>> Gemm(n+1,vector<int>(n+1,0)); // i, j 表示根节点取i值时，二叉搜索树有 j 个数二叉搜索的种数
/**需要的结果是根节点取值为所有n个数范围内的任意一个数i的二叉树的种树的和
**即需要 累加{Gemm[i][n]} 1<=i<=n
** 每一个Gemm[i][j] = 累加{Gemm[k][i-1]} * 累加{Gemm[l][j-i]}
* 所以 递推式是Gemm[i][j]} = 累加{Gemm[k][i-1]} * 累加{Gemm[l][j-i]} 1<=i<=j ; 1<=j<=n; 1<=k<=i; 1<=l<=j-i;
**
**/
//初始化数组
Gemm[1][1] = 1;
Gemm[1][0] = 1;
for(int j = 1; j <=n ; j++){
for(int i = 1; i <= j;i++){
int sum1=0,sum2=0;
for(int k = 1; k<=i-1;k++){
sum1+=Gemm[k][i-1];
}
for(int l = 1; l<=j-i;l++){
sum2+=Gemm[l][j-i];
}
if(!sum1) sum1 = 1;
if(!sum2) sum2 = 1;
Gemm[i][j] = sum1*sum2;
}
}
int sum0=0;
for(int i = 1; i<= n;i++){
sum0+=Gemm[i][n];
}
return sum0;
}
};
#endif
#if 1
class Solution {
public:
int numTrees(int n) {
vector<vector<int>> Gemm(n+1,vector<int>(n+1,0)); // i, j 表示根节点取i值时，二叉搜索树有 j 个数二叉搜索的种数
/**
* 递推式是Gemm[i][j]} = 累加{Gemm[k][i-1]} * 累加{Gemm[l][j-i]} 1<=i<=j ; 1<=j<=n; 1<=k<=i; 1<=l<=j-i;
** 如果这样会有j,i,(k,l) 三层变量的变化，会有三层循环，时间复杂度在n3 但是对于大多数 累加{Gemm[k][i-1]} 和 累加{Gemm[l][j-i]} 都已经计算过，想办法把它们保存下来，使用一个S[j] 来保存 有j个数的二叉树的种数。
**/
//初始化数组
vector<int> S(n+1);
Gemm[1][1] = 1;
Gemm[1][0] = 1;
S[0] = 1;
S[1] = 1;
for(int j = 1; j <=n ; j++){
for(int i = 1; i <= j;i++){
int sum1=0,sum2=0;
if(S[i-1]) sum1 = S[i-1];
else{
for(int k = 1; k<=i-1;k++){
sum1+=Gemm[k][i-1];
}
}
if(S[j-i]) sum2 = S[j-i];
else{
for(int l = 1; l<=j-i;l++){
sum2+=Gemm[l][j-i];
}
}
if(!sum1) sum1 = 1;
if(!sum2) sum2 = 1;
Gemm[i][j] = sum1*sum2;
}
}
int sum0=0;
for(int i = 1; i<= n;i++){
sum0+=Gemm[i][n];
}
return sum0;
}
};
#endif