96. 不同的二叉搜索树

Reference

96. 不同的二叉搜索树 - 力扣（LeetCode）题解 卡特兰数

Problem: 96. 不同的二叉搜索树

思路

dp数组的含义：i个节点有dp[i]种二叉搜索树

递推数组：有n个节点，头节点为j时，左子树有多少种二叉搜索树 x 右子树有多少总二叉搜索树

注意：头节点只能从1开始

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution {
public:
    int numTrees(int n) {
        //dp[i] 表示有i个节点的二叉搜索树有多少种
        vector<int> dp(n + 1, 0);
        //初始化
        dp[0] = 0;dp[1] = 1;dp[2] = 2;
        for(int i = 2; i < n + 1; i++)
            for(int j = 1; j < i + 1; j++) 
                //dp[等于当前以上的节点数量]*dp[剩余的节点数量]
                dp[i] += dp[j-1] * dp[i-j];
        return dp[n];
    }
};

[]

class Solution {

public:

    int numTrees(int n) {

        vector<int> dp(n + 1, 0);

        dp[0] = 1;

        for (int i = 1; i < n + 1; i++) {

            for (int j = 1; j <= i; j++) {

                dp[i] += dp[i - j] * dp[j - 1];

            }

        }

        return dp[n];

    }

};