解法一：动态规划

dp[i] 表示由 i 个结点组成的二叉搜索树的不同结构形式数量。因此，确定子树的结点数后，就可以根据低阶问题的解数量知道子树的不同结构数量。然后左右子树（结点数之和为 n-1 ）进行组合就可以得到结构不同的树（结点数为 n ），这里就是一个乘法原理的问题。

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         // dp[i]表示由i个结点组成的二叉搜索树的不同结构形式数量
  4.         int[] dp = new int[n + 1];
  5.         dp[0] = 1;
  6.         dp[1] = 1;
  7.         for (int i = 2; i <= n; ++i) {
  8.             for (int left = 0, right = i - 1; left <= i - 1; ++left, --right) {
  9.                 dp[i] += dp[left] * dp[right];
  10.             }
  11.         }
  12.         return dp[n];
  13.     }
  14. }