[leetcode]96. Unique Binary Search Trees

https://www.cnblogs.com/zyt1253679098/p/9190217.html

solution 1: calalan数的递归式

注意要换成long，否则会出错

class Solution {
    public int numTrees(int n) {
        long[] dp=new long[n+1];
        dp[1]=1l;
        for(int i=2;i<=n;i++){
            dp[i]=(4*i-2)*dp[i-1]/(i+1);
        }
        return (int) dp[n];
    }
}

solution 2: catalan的直接式

class Solution {
    public int numTrees(int n) {
        
        return (int) (C(2*n,n)/(n+1));
    }
    
    public long C(int n,int m){

        long ans = 1;
        for(int i=1; i<=m; ++i){
            ans *= n--;
            ans /= i;
        }
        return ans;
   
    }
}

solution 2: dp

当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。

当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。

以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+…+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式得出结果。

令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (其中n>=2)

另类递归式：

h(n)=((4*n-2)/(n+1))*h(n-1);
　　该递推关系的解为：

h(n)=C(2n,n)/(n+1) (n=1,2,3,…)

solution 3:

令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (其中n>=2)

public class Solution {
  public int numTrees(int n) {
    int[] G = new int[n + 1];
    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        G[i] += G[j - 1] * G[i - j];
      }
    }
    return G[n];
  }
}