不同的二叉搜索树问题

Question

为什么把 dp[1]=1和dp[2]=2;删除，然后for循环第一层从i=1开始就可以，但是下面那样的代码就过不了？

class Solution {
public:

    int numTrees(int n) 
    {
        vector<int>dp(n+1);//dp[i]表示i个节点有dp[i]种二叉搜索树
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;

        
        for(int i=3;i<=n;i++) //i表示有i个节点，因为要从一个节点开始累计，后面的节点要用到前面的节点
        {
            for(int j=1;j<=i;j++)  //j表示，这i个节点，以j为头节点
            {
                dp[i]=dp[i]+dp[j-1]*dp[i-j];

            }
        }
        
        return dp[n];

    }
};

Answer 1

春风吹又生.c 下午好🌅🌅🌅
本答案参考ChatGPT-3.5

在这个问题中，我们需要计算n个节点可以构建的二叉搜索树的数量。为了解决这个问题，我们可以使用动态规划来求解。

首先，我们定义一个动态规划数组dp，其中dp[i]表示i个节点可以构成的二叉搜索树的数量。

我们观察到，当节点数为0或1时，对应的二叉搜索树的数量都是1，因为只有一个节点或者没有节点时，只有一种情况。所以，我们可以把dp[0]和dp[1]初始化为1。

而当有2个节点时，有2种可能的二叉搜索树：1作为根节点和2作为根节点。所以，我们可以把dp[2]初始化为2。

接下来，对于节点数大于等于3的情况，我们可以使用一个嵌套的for循环来计算dp数组的值。外层循环从3到n，表示有i个节点。内层循环从1到i，表示以j为根节点的情况。

对于每一个节点，我们可以把它作为根节点，然后将其左子树和右子树的节点数量作为子问题来处理。所以，可以使用dp[j-1] * dp[i-j]来表示以j为头节点时的二叉搜索树的数量，其中dp[j-1]表示左子树的数量，dp[i-j]表示右子树的数量。然后，我们累加上述各种情况的二叉搜索树的数量。

最后，我们返回dp[n]作为结果，即n个节点可以构成的二叉搜索树的数量。

下面是修改后的代码：

class Solution {
public:

    int numTrees(int n) {
        vector<int>dp(n+1);//dp[i]表示i个节点有dp[i]种二叉搜索树
        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[i]+dp[j-1]*dp[i-j];
            }
        }
        
        return dp[n];
    }
};

这样的代码可以正确地求解不同的二叉搜索树的数量。去掉dp[1]=1和dp[2]=2是因为在算法的核心部分（嵌套的for循环）中，已经包含了这两种情况的处理。所以，不需要在外围再单独设置dp[1]和dp[2]的值。而从i=1开始循环的方式是错误的，因为在计算dp[i]的时候，需要用到dp[j-1]和dp[i-j]，如果i=1时，j-1和i-j都会越界，导致计算错误。所以，正确的方式是从i=3开始循环。