题目链接

不同的二叉搜索树

题目描述

image.png

实现代码

动态规划思想：记dp[i]表示当n个数时的BST个数；可以将其进行拆分，记F[i,n] 表示当i作为根节点&n个数时的BST个数，因此可以得到公式：

dp[n] = F[1,n] + F[2,n] + … + F[n, n]

而对于F[i, n]而言，可以将其看成左右两个子树的递归， 分成两个树看，因此可得公式：

F[i, n] = G(i-1) * G(n-i)

image.png

实现代码如下：

  1. class Solution {
  2.     public int numTrees(int n) {
  4.         if(n == 1) {
  5.             return 1;
  6.         }
  7.         if(n == 2) {
  8.             return 2;
  9.         }
  11.         int[] dp = new int[n+1];
  12.         dp[0] = 1;
  13.         dp[1] = 1;
  14.         dp[2] = 2;
  15.         for(int i=3; i<=n; i++) {
  16.             for(int j=1;j<=i; j++) {
  17.                 dp[i] += dp[j-1] * dp[i-j];
  18.             }
  19.         }
  21.         return dp[n];
  22.     }
  23. }