动态规划：n 个节点能组成多少不同二叉搜索树

在计算机科学和算法领域，二叉搜索树是一种重要的数据结构。当给定 n 个节点时，计算能组成多少不同的二叉搜索树是一个有趣且具有挑战性的问题，而动态规划是解决这个问题的有效方法。

让我们来理解一下二叉搜索树的性质。在二叉搜索树中，左子树的所有节点值都小于根节点的值，右子树的所有节点值都大于根节点的值。

对于 n 个节点，我们可以从 1 到 n 中选择一个节点作为根节点。当选择 i 作为根节点时，左子树由 1 到 i - 1 共 i - 1 个节点组成，右子树由 i + 1 到 n 共 n - i 个节点组成。

通过动态规划的思想，我们可以定义一个数组 dp[n + 1] 来存储不同节点数能组成的二叉搜索树的数量。

初始情况，dp[0] = 1 （空树也是一种二叉搜索树），dp[1] = 1 （只有一个节点时，只有一种可能的二叉搜索树）。

对于 n 个节点的情况，我们可以通过以下递推公式计算 dp[n]：

dp[n] = ∑ dp[i - 1] * dp[n - i] （其中 i 从 1 到 n）

这个公式的含义是，对于每个可能的根节点 i，左子树的可能性数量为 dp[i - 1]，右子树的可能性数量为 dp[n - i]，两者相乘再累加起来，就得到了 n 个节点能组成的不同二叉搜索树的数量。

例如，当 n = 3 时，选择 1 作为根节点，左子树为空（dp[0] = 1），右子树有 2 个节点（dp[2]）；选择 2 作为根节点，左子树有 1 个节点（dp[1]），右子树有 1 个节点（dp[1]）；选择 3 作为根节点，左子树有 2 个节点（dp[2]），右子树为空（dp[0] = 1）。

通过动态规划的方法，我们可以有效地计算出 n 个节点能组成的不同二叉搜索树的数量，避免了重复计算，提高了算法的效率。

利用动态规划解决“n 个节点能组成多少不同二叉搜索树”的问题，不仅展示了算法设计的巧妙性，也为处理类似的组合问题提供了有益的思路和方法。在实际应用中，这种方法可以帮助我们更好地理解和优化数据结构，提高程序的性能和效率。