leetcode——第96题——不同的二叉搜索树

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

class Solution {
public:
    int numTrees(int n) 
    {
        // 1、确定dp数组的下标及其含义
        // 2、找出递推关系  dp[i] = dp[i] + dp[j - 1]*dp[i-j]
            // dp[j-1]是以 j-1 为头结点左子树节点数量, dp[i-j]是以j为头结点右子树节点数量
            // 后面两项的和 是 n-1 ,因为除去了一个根节点嘛~~~
        // 3、dp数组的初始化
        // 4、确定遍历顺序

        // 这道题的递推·公式比较难想呀~
        /*
        错误一:dp 数组大小为 n+1 ,那么它的最后一个元素就是 dp[n] 嘛!
        错误二:for循环的起始下标是 dp数组初始化后 接下来的那个下标,这个不要写错啦
        错误三:内层 for 循环的终止条件是 j <= i
        */
        vector<int> dp(n + 1, 0);
        dp[0] = 1;

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                // 这里必须是 += 否则就不是你想要的结果
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};
上一篇:算法复习大纲


下一篇:哈尔滨工业大学(威海)校园测速系统Proteus仿真