思路：给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？ 这一题和95. 不同的二叉搜索树 II是一样的，不过这一题求的是个数，不用全部列举出来，理论上是可以使用上一题的代码稍加修改的：
public int numTrees(int n) { if (n < 1) { return 0; } return generateSubtrees(1, n).size(); } private List<TreeNode> generateSubtrees(int s, int e) { List<TreeNode> res = new LinkedList<TreeNode>(); if (s > e) { res.add(null); return res; } for (int i = s; i <= e; ++i) { List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1); List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e); for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; }但是这一题的数据量比较大，所以这样写会超时。我们不妨换个角度，既然只计算个数，那就可以采用动态规划，dp[i] 表示i个节点能组成的二叉搜索树的数量，那么我们可以通过枚举根节点把原二叉搜索树分解为左子树 根 右子树 三部分，那么问题就变成了规模更小的子问题。
但是我们如何更新呢？是固定根节点吗，显然不是，如果固定根节点，其左右可能还未更新，所以我们固定的是一段长度（从dp[i] 表示i个节点能组成的二叉搜索树的数量就可以看出来），然后慢慢更新下标小于i的元素，因此我们需要两层循环，第一层固定节点个数，第二层才固定根节点，这样保证下标小的先得到更新，另外注意初始化：
public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; }