階段の登り方

1 歩で 1 段か 2 段を登れる階段があります。n 段を登り切る道順は何通りあるか、という問題です。

30 段の道順を並べると 130 万通りを超える

4 段なら手で書き出せます。1+1+1+1、1+1+2、1+2+1、2+1+1、2+2 の 5 通りです。5 段で 8 通り、10 段で 89 通り。ここまでは並べられます。しかし 30 段では 1,346,269 通りになり、書き出してから数える方法は破綻します。

数えたいだけなら、道順そのものを作る必要はありません。作らずに数える手が要ります。

最後の 1 歩だけを見れば、2 つに分かれる

n 段目に立っている瞬間を思い浮かべてください。直前にいた場所は、n-1 段目か n-2 段目のどちらかしかありません。1 歩で 3 段は登れないからです。

n-1 段目までの道順それぞれに「最後に 1 段」を付ければ n 段目の道順になり、n-2 段目までの道順それぞれに「最後に 2 段」を付けても n 段目の道順になります。この 2 つのグループは重なりません。最後の 1 歩の大きさが違うので、同じ道順が両方に入ることはないからです。だから、2 つの個数を足したものが答えです。

出発点は手で決めます。1 段なら 1 の 1 通り。2 段なら 1+1 と 2 の 2 通りです。ここさえ置けば、3 段目から先は足し算だけで順に決まります。

本当にそうなるか、小さいところで確かめます。3 段は 2 通りと 1 通りを足して 3 通り。手で書き出すと 1+1+1、1+2、2+1 の 3 通りで合っています。4 段は 3 通りと 2 通りを足して 5 通りで、最初に書き出した 5 通りと一致します。ここまで合えば、あとは同じ足し算を 30 段まで繰り返すだけです。

足し算であって、掛け算ではない

「n-1 段目までの道順が x 通りあって、そこからもう 1 歩」と考えると、つい掛けたくなります。しかし n-1 段目から来る場合、最後の 1 歩は 1 段の 1 通りに決まっています。選択肢が増えるのではなく、既にある道順の末尾が伸びるだけです。増えるのは長さであって、通り数ではありません。

0 段目の扱いにも注意してください。f(0) を 0 としてしまうと f(2) が合わなくなります。1 段目と 2 段目を出発点として直接置いてしまうのが確実です。

やってみよう

climbStairs(n) を書いてください。1 段目と 2 段目の答えを先に置き、3 段目から n 段目までを、1 つ前と 2 つ前の和で順に埋めます。再帰ではなくループで組み立ててください。n が 30 でも一瞬で返れば成功です。出てきた数の並びがどこかで見た数列になることに気づいたら、それは正解のしるしです。

1. f(1) = 1、f(2) = 2 を基底ケースにする
2. f(n) = f(n-1) + f(n-2) の漸化式に従って DP 配列を埋める
3. 再帰の代わりにループで実装し、n >= 30 でも一瞬で返ること