LeetCode96：不同的二叉搜索树

题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

代码

/*
       dp[i]：表示i个节点有dp[i]个不同的二搜索叉树

       递推公式：dp[i] += dp[j-1] * dp[i-j], j代表头节点 dp[j-1]代表左子树的形态个数
                                                         dp[i-j]代表右子树的形态个数
       初始化：dp[0] =1 , dp[1] = 1, dp[2] = 2;

       遍历顺序：从小到大


*/
class Solution {
public:
    int numTrees(int n) {
        if (n == 0) return 1;
        else if (n <= 2) return n;
        vector<int> dp(n + 1);
        dp[0] = 1, dp[1] = 1, dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        int  result = 0;
        for (int num : dp)
            result += num;

        return result;
    }
};