Leetcode96:不同的二叉搜索树（动态规划）

来源

分析：

 　　遍历1..n，以i为根的二叉搜索树的个数=左子树中不同的二叉搜索树的数量 * 右子树中不同的二叉搜索树的数量

　　$G(n) = \sum\limits_{i = 1}^n {F(i,n)} $　　G(n)表示有个结点的不同的二叉搜索树的个数，F(i,n)表示以i为根节点且有n个结点的不同的二叉搜索树的个数

　　$F(i,n) = G(i - 1)*G(n - i)$

　　$G(n) = \sum\limits_{i = 1}^n {F(i,n)}  = \sum\limits_{i = 1}^n {G(i - 1)*G(n - i)}$

方法1：递归

 1 class Solution {
 2     public int numTrees(int n) {
 3         int nums = 0;
 4         if(n==1){
 5             return 1;
 6         }
 7         for(int i = 1; i< n+1 ; i++){
 8             nums += numTrees(i-1)*numTrees(n-i);
 9         }
10         return nums;
11     }
12 }

方法2：动态规划

dp[n]表示n个结点的不同的二叉搜索树的数量

初始时：dp[0]=1, dp[1]=1

填表dp[2..n]，对于每一个dp[i]，dp[i]=dp[0]*dp[i]+dp[1]*dp[i-1]+...=sum(dp[j-1]*dp[i-j]) (j=1..i)

 1 class Solution {
 2     public int numTrees(int n) {
 3         int[] dp = new int[n+1];
 4         dp[0]=1;
 5         dp[1]=1;
 6         //填动态规划表,从dp[2]填到dp[n]
 7         for(int i = 2; i ){
 8             for(int j = 1; j<=i;j++){
 9                 dp[i] += dp[j-1]*dp[i-j];
10             }
11         }
12         return dp[n];
13     }
14 }