SRM401 Div1 250

DP。カタラン数。境界線を超えてはいけない経路の数。
DPやカタラン数の良い演習問題。

countDiagrams

class FIELDDiagrams {

public:
	long long countDiagrams(int fieldOrder) {

		long long partition[45][45] = {0};
		for(int i=1; i<=fieldOrder; i++){
			partition[0][i] = 1;
		}

		for(int i=1; i<=fieldOrder; i++){
			for(int j=0; j<=fieldOrder; j++){
				if(partition[i-1][j] != 0){
					for(int k=0; k<=min(fieldOrder-i,j);k++){
						partition[i][k] += partition[i-1][j];
					}
				}
			}
		}

		return partition[fieldOrder][0];
	}
};