9.26 动态规划---二叉搜索树

题目：给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

首先需要明确的是，因为是从1~n,所以从任意一个地方提起该数列，都能构成一棵二叉搜索树，即左子树小于根节点，右子树大于根节点。

比如提起i，左边构成i-1,右边构成n-i。那i-1和n-i其实又可以继续分成子问题。

假设f(n) = 我们有n个数字时可以构建几种搜索树，需要注意的是，数字其实不重要分为左子树和右子树之后我们只需要统计个数就可以了，123和456其实都一样的。

我们来看[1,2,3]

如果提起1作为树根，左边有f(0)种情况，右边f(2)种情况，左右搭配一共有f(0)f(2)种情况
如果提起2作为树根，左边有f(1)种情况，右边f(1)种情况，左右搭配一共有f(1)f(1)种情况
如果提起3作为树根，左边有f(2)种情况，右边f(0)种情况，左右搭配一共有f(2)f(0)种情况
容易得知f(3) = f(0)f(2) + f(1)f(1) + f(2)f(0)
(注：这里的f(0)可以理解为=1也可以理解为=0，这个不重要，我们这里理解为=1,即没有数字时只有一种情况，就是空的情况）

class Solution {
public:
    int numTrees(int n) {

        vector<int> dp(n+1,0);//因为需要添加 dp[0] 这个变量，使其等于1，会使计算更方便

        dp[0] = 1;

        for(int i = 1 ; i <= n ;i++ )//序列个数，也就是树的节点数
        {
            for(int j = 1 ; j <=i ; j++)//提起的根节点
            {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }

        return dp[n];

    }
};