1. 問題

p986.jpg

上記のグラフにおいて、左のほうでは、高さ3でのピークが2、高さ2でのピークが2である。右のほうでは、高さ1, 2, 3でのピークはそれぞれ1である。
 グラフでは、パスは原点(0,0)から出発し、ステップ(1,1)と(1,-1)に沿って右へ移動し、最終的に(2n,0)にもどる。パスはx軸を切って下に移動することはない。
 n (1<=n<20)、および高さk (1<=k<20) でのピーク数がちょうどr (0<=r<20) であるパスの数を示せ。

2. 計算法
 本問題もDPによる方法を考える。
 高さkのところのピース数がrであるパスが右上がり(つまりステップ(1,1))で (x,y) に来た時の数を c[x][y][r][k][1] とし、右下がり(ステップ(1,-1))のパス数を c[x][y][r][k][0] とする。
 配列の大きさは c[40][21][21][20][2] になる。
 初期値 c[1][1][0][k][1] = 1 (1<=k<20)、他の要素はゼロ。
 漸化式は以下の通り。

入力の値n, r, kに対する答えは c[n+n][0][r][k][0] である。

3. 検証用入出力データ

4. 感想
 DPの表現式(配列)をちゃんとつくっておけば、複雑な問題ではなさそう。

Comments are closed.

Post Navigation