Expressions UVA-10157(数学+繰返しの組合せ)

Expressions UVA - 10157
タイトル:
n個の括弧をあげて、合法的なマッチングを求めて、深さはdの組み合わせの数を超えません.
分析:
組み合わせ、カウント、dp、大きな整数.
このテーマはカトラン数に似ているが、深さには制限があり、カトラン数の繰返し式を利用して解くことができる.
DP(k,d)をk対括弧形成深さがdを超えない合法的なマッチング方法数とする.
DP(k,d)= Σ(DP(i,d-1)*DP(k-1-i,d){i 0からk-1}
(カトラン数で押すと、k対括弧は2つのグループに分けられ、左側i個はシリアルAを生成し、右側k-1-i個はシリアルBを生成し、
もう1対はAの外で、(A)Bの形式を形成します;この時Aの深さは最大でd-1で、Bの深さは最大でdです)
従って、深さdのスキーム数は、DP(k,d)−DP(k,d−1)である.
code:

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
	static Scanner cin = new Scanner(System.in);
	static BigInteger[][] f = new BigInteger[151][151];
	static boolean[][] vis = new boolean[151][151];
	
	static BigInteger DP(int n,int d) {
		if(vis[n][d]) 
			return f[n][d];
		vis[n][d] = true;
		if(n <= 1 || d <= 1)
			return f[n][d] = BigInteger.ONE;
		f[n][d] = BigInteger.ZERO;
		for(int i = 0; i < n; i++) 
			f[n][d] = f[n][d].add(DP(i,d-1).multiply(DP(n-i-1,d)));
		return f[n][d];
	}
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        for(int i = 0; i < 151; i++) {
        	f[i][0] = f[i][1] = f[0][i] = f[1][i] = BigInteger.ONE;
        	for(int j = 0; j < 151; j++) {
        		vis[i][j] = false;
        	}
        }
        while(cin.hasNext()) {
        	int n = cin.nextInt();
        	int d = cin.nextInt();
        	if(n <= 2 || d <= 1) {
        		System.out.println("1");
        		continue;
        	} 
        	n >>= 1;
        	DP(n,d);
        	DP(n,d-1);
        	System.out.println(f[n][d].subtract(f[n][d-1]));
        }
    }

}