LeetCode(94)Unique Binary Search Trees

제목은 다음과 같습니다.
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

분석은 다음과 같습니다.
처음에는 이 문제가 너무 어려워 보였어요.나중에 힌트를 보고 귀환을 했습니다.나중에 생각해 보니 역귀환으로 아주 쉽게 다 썼다.n개의 나무가 있다.그러면 BST의 루트 수치만 고찰할 가능성은 n개입니다.BST의 루트가 i라고 가정하면 i를 루트로 하는 BST의 총 수량은 그의 왼쪽 트리와 오른쪽 트리에 달려 있다. 구체적으로 말하면 왼쪽 트리의 수량과 오른쪽 트리의 수량의 곱셈이다.그럼 왼쪽 나무의 수는 몇 개일까요?오른쪽 나무의 수량은 몇 개입니까?이 문제는 아까의 문제와 완전히 같기 때문에 이렇게 하면 귀속이 된다.base case는 n=0 또는 n=1일 때 BST 수량이 1개밖에 없는 것이 분명합니다.
내 코드:

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

요약은 다음과 같습니다.
(1) 본 문제의 핵심은 카틀란수 문제이다. 카틀란수 문제는 아직도 많다. 예를 들어LetCode에 괄호 문제가 있는데 그 본질도 카틀란수 문제이다. 지금은 이해가 잘 안 된다. 이따가 카틀란수 문제를 정리한다.
(2) 귀환의 용도를 다시 발견했다. 앞으로 머리가 잘 돌아가지 않는 문제는 귀환으로 시험해 볼 수 있는지 생각해야 한다. 기계와 사람이 비교할 수 있는 장점도 발휘해야 한다.
update: 2014-10-06 
귀속을 교체로 바꾸고 공간으로 시간을 바꾸면 일부 운행 시간을 줄일 수 있다.

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

update: 2015-03-23
1.현재 귀속 제출은 이미 TLE입니다.
2. 그룹을 초기화하는 더욱 간결한 표현은 다음과 같다.

        int* array = new int[n + 1](); //() ， memeset(array, 0, sizeof(int) *(n + 1));

코드는 다음과 같습니다.

//2ms
class Solution {
public:
    int numTrees(int n) {
        int* array = new int[n + 1](); //() ， memeset(array, 0, sizeof(int) *(n + 1));
        array[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                array[i]+=array[j] * array[i - j - 1];
            }
        }
        int result = array[n];
        delete [] array;
        return result;
    }
};