１０歳の動的計画 (AOJ 2335)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335

問題

略

解法

右方向に寄り道する回数をi回とする。この時左右方向の進み方はカタラン数の計算方法を応用して計算するとCombination(n+2*i,i) - Combination(n+2*i,i-1)になる。上下方向も同様に計算でき、二つを掛け合わせる際に左右と上下の並べ替えの方法としてCombination(n+m+2*k,n+2*i)を掛ければよい。あとは右方向に寄り道する回数を全部試す。