HDU 1130（Catalan数的应用）

题目大意：就是给你1到N个数，让你求他能构成多少种二叉树；

题目分析：这里又是一种组合数学里的重要知识点！Catalan数的应用。

如果数据比较小，建议模拟这个公式：

Catalan的原始递推公式就是这个，这个是专门针对给出节点，有多少二叉数构造方法的方程。

=+

用二维数组模拟，当前元素的值等于他正上方的值+左边的值；

当然所消耗的内存是很大的 ：M*N*4 Bytes,所以数字小才能模拟50以内比较保险 哈哈{^_^}！

然后大数的就只有应用到大数的算法啦，反正我认为C++里的模拟太费事了 ，所以今天第一次也学习写

JAVA里的大数的运算了， 建议您也学学，嘿嘿，方便啊 。

首先分析一下思路：

这个方程进一步化简：

F( N )=    （k=0....N-1）

根据这个公式进行计算就可以了

import java.math.*;
import java.util.*;
public class Main{
	public static void main(String args[]){
		List list=new ArrayList(101);
		BigInteger f=BigInteger.valueOf(1);
		list.add(f);
		list.add(f);
		for(int i=2;i<=100;i++){
			f=BigInteger.valueOf(0);
			for(int j=0;j<i;j++)
				f=f.add(((BigInteger)list.get(j)).multiply( (BigInteger)list.get(i-1-j)));
			list.add(f);
		}
			Scanner cin=new Scanner(System.in);
			int inputInt=0;
			while(cin.hasNext()){
				inputInt=cin.nextInt();
				System.out.println(list.get(inputInt));
			}
	}
}