96.Unique Binary Search Trees

96.Unique Binary Search Trees

這題是動態規劃的題目，因為自己看不懂自己寫的，慚愧做個紀錄
題意是給你n，要回傳n有幾個獨一無二的二元樹

已經知道如果n=1, ans=1
n=2, ans=2
n=3, ans=5
n=4, ans=? 4就比較難直接想出來了

可以看看下面的圖

第一行的數字代表樹的根
第二行的數字代表展開的樹高

以n=4來觀察
以1來說，一定是任何數字都比它大，其他的樹一定是在右邊
以4來說，一定是任何數字都比它小其他的樹一定是在左邊
以2來說，左邊的樹高是1，右邊的樹高是2
然後左右的樹互乘，就可以得到此根所擁有的獨一無二的二元樹

然後這邊必須把高度是0的樹，用1去乘，為了方便做計算

public int numTrees(int n) {
  int[] nums = new int[Math.max(n+1, 4)]; //n+1 因為索引0已經拿來計算用了  
  nums[0] = 1;  //給1為了方便計算
  nums[1] = 1;
  nums[2] = 2;
  nums[3] = 5;
  if( n <= 3)
      return nums[n];

  int count, start, end;
  for (int i = 3; i < n; i++) {
      count = 0;
      start = 0;
      end = i;
      for (int j = 0; j < (i+1)/2; j++) {  //這邊除以2，因為樹是對稱的，不用把後半繞完
          count += nums[start++] * nums[end--];
      }
      count *= 2; //因為剛剛只有算一半，乘回來
      if(((i+1)&1) > 0){ //遇到如果是奇數的樹，就不對稱了，要把中間的根乘兩次
          count += Math.pow(nums[(i+1)/2], 2);
      }
      nums[i+1] = count;
  }
  return nums[n];
      
}