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]; } };