问题描述：
N对括号能够得到的有效括号序列有哪些？
如N=3时，有效括号串共5个，分别为：
()()(), ()(()), (())(), (()()), ((()))
问题分析：
任何一个括号，都可以写成A(B)：
- A， B都若干括号对形成的合法串（可以为空串）；
- 若N=0，括号序列为空；
- 若N=1，括号序列只能是()一种。
当0<=i<=N-1时，：
- 计算i对括号的可行序列A；
- 计算N-i-i对括号的可行序列B；
- 组合得到A(B)。
可以用递归的方法解决问题，但是在coding时出现了各种各样的问题，所以我决定还是用非递归的方法解决，
但是需要用额外的空间来存储之前计算的结果。
code:
/*** Given the number N, return all of the correct brackets.* @param n* @return*/@SuppressWarnings("unchecked")public static ArrayList<String> getBracketsOfN(int n) {@SuppressWarnings("rawtypes")ArrayList[] dp = new ArrayList[n+1];for(int i=0; i<dp.length; i++)dp[i] = new ArrayList<String>();dp[0].add("");dp[1].add("()");if(n == 0) return dp[0];if(n == 1) return dp[1];int count = 2;while(count < n+1) {ArrayList<String> lcount = dp[count];for(int i=0; i<count; i++) {ArrayList<String> l1 = dp[i];ArrayList<String> l2 = dp[count-i-1];for(int j=0; j<l1.size(); j++) {for(int k=0; k<l2.size(); k++) {StringBuffer sb = new StringBuffer();sb.append(l1.get(j));sb.append("(");sb.append(l2.get(k));sb.append(")");lcount.add(sb.toString());}}}dp[count++] = lcount;}return dp[n];}
Catalan数。
通过上面额分析可以看到，当输入的n从1开始，构成的数刚好为卡特兰数，分析括号种数形成的数列，可以得出卡特兰数的形成过程。（使用DP）
code：
/*** Get the nth Catalan number.* @param n* @return*/public static int getCatalanNumber(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i=2; i<n+1; i++) {int t = 0;for(int j=0; j<i; j++) {t += dp[j] * dp[i-j-1];}dp[i] = t;}return dp[n];}
