Leetcode:unique_binary_search_trees

Leetcode:unique_binary_search_trees

一、 題目

給定數n，問有多少種不同的BST(二叉搜索樹)

例如:

由於N =3，共有5種獨特的BST。

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

二、分析

要求一定的二叉查找樹的數量，我們知道二叉查找樹可以任意取根。從處理子問題的角度來看，選取一個結點為根，可把結點分成左右子樹，以這個結點為根的可行二叉樹數量就是左右子樹可行二叉樹數量的乘積，所以總數量是將以所有結點為根的可行結果累加起來。

看到有人說到卡特蘭數，這正是卡特蘭數的一種定義方式，是一個典型的動態規劃的定義方式。

卡特蘭數的一半公式為Cn= 1/(n+1)*(2n,n) = (2n)!/{(n+1)!*n!}

class Solution {
public:
    int numTrees(int n) {
        int flag=1;
        for(int i=2;i<=n;i++) {
        	flag=2*(2*i-1)*flag/(i+1); 
        }
        return flag;
    }
};

二:

 
class Solution {
public:
	int numTrees(int n) 
	{
		return numTrees(1,n);
	}

	int numTrees(int start, int end)
	{
		if (start >= end)
			return 1;

		int totalNum = 0;
		for (int i=start; i<=end; ++i)
			totalNum += numTrees(start,i-1)*numTrees(i+1,end);
		return totalNum;
	}
};




class Solution {
public:
	int numTrees(int n) {
    	if (n < 0) return 0;
           vector trees(n+1, 0);
        trees[0] = 1;

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