本文共 944 字，大约阅读时间需要 3 分钟。

给定n，如何计算存储值1到n的所有不同的二叉搜索树（BST）的个数？

问题分析

这是一个经典的动态规划问题，涉及计数全局不同的二叉搜索树的数量。当n=3时，可以有5种不同的 BST，这一点很直观。

动态规划解法

我们设dp[i]表示使用1到i值构造的所有全局不同 BST的数量。我们可以通过以下方式计算：

解释

这个动态规划方法通过逐渐构建 BST，从简单情况开始，逐步解决复杂情况。状态转移方程考虑了 BST 的构造方式，即每个可能的根节点以及其左右子树的可能性。这种方法的时间复杂度是 O(n²)，空间复杂度为 O(n)。

代码实现

public class Solution {    public int numTrees(int n) {        int[] dp = new int[n + 1];        dp[0] = 1;        dp[1] = 1;        for(int i = 2; i <= n; i++) {            for(int j = 0; j < i; j++) {                dp[i] += dp[j] * dp[i - j - 1];            }        }        return dp[n];    }}

注意事项

• 初始化：确保dp数组的大小为n+1，避免越界。
• 循环条件：外层循环从i=2到n，内层循环j从0到i-1。
• 结果计算：dp[i]的值直到i=n时才得到最终结果。

这个解法使用动态规划高效地解决了问题，并确保了在整数范围内的正确性。