Leetcode --- Unique Binary Search Trees I(Medium)
===

## Description
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

==n個node可以組成多少不同構的BST==

### Example

* Ex1:
**Input**: n = 2
**Output**: 2
* Ex2:
**Input**: n = 3
**Output**: 5
* Ex3:
**Input**: n = 4
**Output**: 14

### Constraint
* 1 <= n <= 19

## Solutions (DP solution)

取n=3做範本,看能否找出適合的解

1          1            2           3         3
 \          \         /   \        /         /
  2          3       1     3      1         2
   \        /                      \       /
    3      2                        2     1

先分解大問題 =>
整個n=3的case 可拆成 : root=1,2,3分別的所有解
Sol(n=3) = sol(root =1) + sol(root =2) + sol(root=3)

再來解小問題 =>
* 當root =1:
依BST規則 左子<1 : 為空, 右子>1 : (2,3) ,
而2,3做不同BST等於於1,2做不同BST的解,所以sol({2,3}) = sol(n=2)
* 當root =2:
左子有1,右子有3 無其他選擇
* 當root =3:
左子有1,2 ,右子為空 ,sol({1,2}) =sol(n=2)

最後把上面結論化成通式 =>
當n=3 : sol(root =1) + sol(root =2) + sol(root=3)
* sol(root=1):
左子為空有sol(n=0)=1種組合,右子為{2,3}有sol(n=2)=2種組合 => 可組合數 ==sol(n=0)*sol(n=2)== =2
* sol(root=2):
左子為1有sol(n=1)=1種組合,右子為3有sol(n=1)=1種組合 => 可組合數 ==sol(n=1)*sol(n=1)== =1
* sol(root=3):
左子為{1,2}有sol(n=2)=2種組合,右子為空有sol(n=0)=1種組合 => 可組合數 ==sol(n=2)*sol(n=0)== =2

==通式 => sol(n=3) = sol(n=0)*sol(n=2) + sol(n=1)*sol(n=1) + sol(n=2)*sol(n=0) = 5==

換個表示式 =>
==f(n) = f(0)*f(n-1) + f(1)*f(n-2)+ ... + f(n-1)*f(0)==

此式子即為大名鼎鼎的**Catalan Number** =>


### Implement code
* method 1 : Recursion

class Solution {
    public int numTrees(int n) {
        if(n==0)
            return 1;
       
        int ans =0;
        int[] mem = new int[n];
        mem[0]=1;
        for(int i =0;i<n;i++)
        {
            if(mem[i] == 0)
                mem[i]= numTrees(i);
            if(mem[n-1-i]==0)            
                mem[n-1-i] = numTrees(n-1-i);
            
            ans += mem[i] *mem[n-1-i];
        }
        return ans;
    }
}

line 12 ~ 14 : 為memorize的操作,若已有值則不再遞迴尋找一次.

#### Submission on Leetcode
Runtime:**4 ms, faster than 5.00%** of Java online submissions for Unique Binary Search Trees.

已做memorize的操作了為什麼還這麼慢?
實際trace: 當n=3要抓取n=2時會進遞迴,而n=2會抓取n=1的遞迴,但跑完回到n=3時,只會存n=2的解,因為n=1為n=2的區域變數,造成下次要抓取n=1解時又要再跑一次遞迴 ,當n變大時就會造成很多地方要重跑

* method 2 : Recursion(**modification**)

class Solution {
    public int numTrees(int n) {
    
        if(n==0)
            return 1;
        int[] mem = new int[n+1];
        mem[0]=1;
        return helper(n,mem);
    }
    private int helper(int n ,int[] mem)
    {
        int ans =0;
        for(int i =0;i<n;i++)
        {
            if(mem[i] == 0)
                mem[i]= helper(i,mem);
            if(mem[n-1-i]==0)            
                mem[n-1-i] = helper(n-1-i,mem);
            
            ans += mem[i] *mem[n-1-i];
        }
        return ans;
    }
}

把mem陣列當作輸入變數,再java中會是類call by reference的操作,所以當某個地方改變,大家都會改變.

#### Submission on Leetcode

Runtime: **0 ms, faster than 100.00%** of Java online submissions for Unique Binary Search Trees.
Memory Usage: **36 MB, less than 26.00%** of Java online submissions for Unique Binary Search Trees.

速度確實變快了

* Method 3 : Iterative

class Solution {
    public int numTrees(int n) {

        int[] mem = new int[n+1];
        mem[0]=1;
        for(int i =0;i<=n;i++)
        {
          for(int j =0;j<i;j++)
          {
             mem[i] += mem[j]*mem[i-1-j];
          }
        }
        return mem[n];
    }
   
}

核心想法為,從小的n慢慢漲到大的n

#### Submission on Leetcode
Runtime: **0 ms, faster than 100.00%** of Java online submissions for Unique Binary Search Trees.
Memory Usage: **35.7 MB, less than 62.37%** of Java online submissions for Unique Binary Search Trees.

###### tags: `Leetcode` `Medium` `DP` `Catalan Number`