구성할 수 있는 두 갈래 찾기 트리의 개수 Unique Binary Search Trees

제목은 Leetcode에서 유래했다.
제목: Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.

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

사고방식: 차례차례 사상.하나의 수 k를 뿌리 노드로 선택하면 k보다 작은 수는 왼쪽 나무에서, k보다 큰 수는 오른쪽 나무에 있다.모두 n가지 선법이 있다.
방법1: 귀속법.

class Solution {
public:
    int numTrees(int n) {
        if(n==0)
            return 1;
        else
        {
            int i;
            int num=0;
            for(i=0;i<n;i++)
            {
                num += numTrees(i) * numTrees(n-i-1);
            }
            return num;
        }
    }
};

방법2:교체법.귀속법에는 중복된 계산이 나타나기 때문에 1차원 동적 기획법으로 기록한다.

class Solution {
public:
    int numTrees(int n) {
        int H[n+1];
        memset(H, 0, sizeof(H));
        H[0] = 1;
        H[1] = 1;
        for(int i=2;i<=n;i++)
            for(int j=0;j<i;j++)
                H[i] += H[j] * H[i-j-1];
        return H[n];
    }
};

주의: 이 수열은 피보나치 수열보다 더 빨리 늘어나는 것 같아서 스스로 쓰면 롱롱 타입이 좋아요.