题目描述

给定一个值n，能构建出多少不同的值包含1…n的二叉搜索树（BST）？
例如
给定 n = 3, 有五种不同的二叉搜索树（BST）

代码

思路和21题一样，通过数学归纳找规律

  1. public static int numTrees (int n) {
  2.         if(n>1) {
  3.             int[] arr = new int[n+1];
  4.             arr[0] = 1;
  5.             arr[1] = 1; 
  6.             for(int i=2;i<=n;i++) {
  7.                 for(int k=1;k<=i;k++) {
  8.                     arr[i] += arr[k-1]*arr[i-k];
  9.                 }
  10.             }
  11.             return arr[n];
  12.         }else {
  13.             return 1;
  14.         }
  17.         // write code here
  18.     }