

public class Maerz16_dynProg {
	public static void main(String[] args) {
		int testlaenge=15;
		System.out.println("Start Test ...");
	
		for(int i=1; i<= testlaenge; i++){
			System.out.print("a("+i+") = "+a(i));
			org.junit.Assert.assertEquals(a(i),aDP(i));
			System.out.println(" = aDP("+i+")");
			
		}
		System.out.println("Test OK");
	}
	public static long a(int n){
		if (n <= 1){
			
			return 1;
		}else{
			long an=0;
			
			for(int i=1; i < n; i++){
				an=an+(a(i)*a(n-i));
			}

			return a(n-1)+an;
		}
		
	}
	
	static long[] mem;
	
	public static long aDP(int n){
		if(mem == null || n >= mem.length){
			long[] oldMem=mem;
			mem=new long[n+1];
			
			if(oldMem != null){
				for(int i=0; i < oldMem.length;i++)
				mem[i]=oldMem[i];
			}
			
		}
		
		if(n <= 1){
			mem[n]=1;
		
		}else if(mem[n] == 0){
			
			mem[n]=aDP(n-1);
			
			for(int i=1; i