本文共 1933 字，大约阅读时间需要 6 分钟。

class Solution {//a combinatorial mathematics problem //Firstly, this kind of problem generally can be modeled as famous number, here is catalan number//Secondly, If we do not have such a background, I think it will be totally fine if we can find //the transform equation or the regular pattern.//analysis://we pick a node i as a root in the BST, then the size of left subtree is i-1, and the size of //right tree is n-i, though the number in right tree may be different from 1 2 ... n-i, but actually//it is equal to the sequence of that in such a problem.//Now we should figure out that, if j is not equal to i, is there any duplicate(same) case?//I think there will be no same case, because the root is different that will be enough to prove this.//So, the equation will be f(size)=sum of f(i-1)*f(size-i), where 1<=i<=size. //initialize: f(0)=1, f(1)=1 public:	int DP(int n)	{		if(n <= 1)			return 1;		vector
   
     f(n+1, 0);		f[0] = f[1] = 1;		for (int size = 2; size <= n; ++size)		{			for (int i = 1; i <= size; ++i)			{				f[size] += f[i-1]*f[size-i];			}		}		return f[n];	}	int numTrees(int n) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		return DP(n);	}};
   

second time

class Solution {public:    int numTrees(int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
   
    
      > f(n, vector
     
      (n, 0));        for(int i = 0; i < n; ++i) f[i][i] = 1;        for(int len = 2; len <= n; ++len)        {            for(int i = 0; i < n; ++i)            {                int j = len-1+i;                if(j >= n) break;                for(int k = i; k <= j; ++k)                {                    if(k == i) f[i][j] += f[k+1][j];                    else if(k == j) f[i][j] += f[i][k-1];                    else f[i][j] += (f[i][k-1]*f[k+1][j]);                }            }        }        return f[0][n-1];    }};
     
    
   

转载地址：http://chxti.baihongyu.com/