LettCode 96. 不同的二叉搜索树

LettCode 96. 不同的二叉搜索树
思路：
对于一个长度为n的序列，不管里面的数字是多少，比如是1~n，记可以构造的二叉搜索树个数为sum，则当序列为2~n+1的时候，二叉搜索树的个数不会发生变化，所以我们只需要枚举每一段长度即可。
f[i]状态表示为长度为i的序列可以构成的二叉搜索树的个数，状态计算为f[i] += f[j-1] * f[i-j],即左边的二叉搜索树的个数乘以右边二叉搜索树的个数。

代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n+1);
        //比如j取1 左边是f[0] 右边是f[i] 有右边不是0 最后的答案f[i] = f[0] * f[i] 所以f[0] = 1
        f[0]=1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                f[i] += f[j-1] * f[i - j];
            }
        }
        return f[n];
    }
};