【LeetCode】96. 不同的二叉搜索树（中等）——代码随想录算法训练营Day40

题目链接：96. 不同的二叉搜索树

题目描述

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

文章讲解：代码随想录

视频讲解：动态规划找到子状态之间的关系很重要！| LeetCode：96.不同的二叉搜索树_哔哩哔哩_bilibili

题解1：动态规划

思路：将任意一个节点作为根节点，设左子树节点数为 j，则右子树节点数为 n - j，左子树的数量相当于 j 个节点组成的二叉搜索树数量，右子树的数量相当于 n - j 个节点组成的二叉搜索树的数量，左子树为 j 时二叉搜索数的数量即为 j  和 n - j 个节点组成的二叉搜索树数量乘积。n 个节点的二叉搜索树数量即为 j 从0到n - 1时左子树为 j 个节点时时二叉搜索数的数量和，n 的状态依赖于 j 从 0 到 n - 1 时 j 的状态和 n - j 的状态，因此可以使用动态规划法。

动态规划分析：

• dp 数组以及下标的含义：dp[i] 代表由 n 个节点组成且节点值从1到 n 互不相同的二叉搜索树有多少种。
• 递推公式：dp[i] += dp[j] * dp[i - j - 1]
• dp 数组初始化：
• 遍历顺序：从前到后。
• 打印 dp 数组：dp 数组从下标0开始为1、1、2、5、14、42、132、429。

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        // 以任意一个节点为头节点，设左子树节点数为 j，则右子树节点数为 i - j - 1
        let j = 0;
        while (j <= i / 2 - 1) {
            dp[i] += dp[j] * dp[i - j - 1] * 2;
            j++;
        }
        if (i % 2 === 1) {
            dp[i] += dp[j] * dp[j];
        }
    }
    return dp[n];
};

分析：时间复杂度为 O(n²)，空间复杂度为 O(n)。

收获

本题的难点在于想到要使用动态规划法以及递推公式的分析，n 的状态依赖于前面所有数的状态。