Climbing Stairs
あなたはn段の階段の一番下にいます。1回の移動で1段または2段上ります。移動の順序が異なる場合、上り方は別々に数えるため、1, 2と2, 1は2通りです。関数はnを受け取り、頂上まで到達する異なる方法の数を返します。
関数
- ninteger
- 階段の段数
- 戻り値integer
- 段階 n に到達する、1 段階と 2 段階からなる異なる並びの数
制約
1 ≤ n ≤ 45- 答えは符号付き32ビット整数に収まります。
n = 45の場合、1836311903になります。
例
- 入力
- n = 3
- 出力
- 3
- 説明
- 3段の階段は、
1, 1, 1、1, 2、または2, 1のように上ることができるので、3通りの方法があります。
- 入力
- n = 5
- 出力
- 8
- 説明
- ステップ5への登り方はすべて、ステップ4からの1ステップ（そこに到達する方法は5通り）か、ステップ3からの2ステップ（方法は3通り）で終わるため、答えは
5 + 3 = 8です。
提出時に隠しテスト+13件
発展問題
いくつかの段が壊れていて、そこには決して立てないとしたらどうでしょうか？漸化式はどのように変わり、壊れた段の数え方はどうなりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
段数
nまでのどの登りについても、最後の一歩を見てみましょう。その直前には、どこに立っていた可能性があるでしょうか？ステップ
nまでの登り方はすべて、ステップn-1からの1段登り、またはステップn-2からの2段登りのどちらか一方で終わります。したがって、nの登り方の数は、n-1の登り方の数とn-2の登り方の数の合計です。1段の歩数（1通り）と2段の歩数（2通り）から始め、順に大きくしていきます。必要なのは常に直前の2つの数だけで、新しい数はその合計です。
解説
すべての登り方を列挙する方法はうまくいきません。45段の階段には、1836311903通りの登り方があるからです。手がかりは最後の一歩です。段 n までの登り方は、終わる直前に必ず段 n-1 または段 n-2 を通ります。これにより、ways(n) = ways(n-1) + ways(n-2) というフィボナッチ数列の漸化式が得られます。小さい値から順に計算すれば、必要なのは2つの変数だけです。
最後の動きに対する単純な再帰
正しいが、最大のテストでは終わらない
考え方
最後の移動ごとに、ステップ n までの登り方を分けます。1段で終わる登り方では、その前にステップ n-1 に立っており、そのような登り方は ways(n-1) 通りあります。2段で終わる登り方では、ステップ n-2 に立っており、そのような登り方は ways(n-2) 通りあります。すべての登り方はどちらか一方で終わり、両方で終わることはないため、ways(n) = ways(n-1) + ways(n-2) となります。
再帰には2つの基底ケースが必要です。1段なら登り方は1通り、2段なら登り方は2通り（1, 1 と 2）です。どちらの場合も答えは n と等しいため、n ≤ 2 のときは関数が n を返し、それ以外の場合は合計を返します。
答えは正しいものの、計算量が爆発的に増えます。climbStairs(5) はステップ3を2回、ステップ2を3回求め、合計で9回呼び出します。呼び出し回数は答えと同じように増加します。n = 45 の場合、関数は2269806339回、つまり約 2.3 × 10^9 回呼び出され、制限時間内では到底間に合いません。再帰の深さは n レベルにすぎないため、スタックが使用する空間は O(n) です。
アルゴリズム
n ≤ 2の場合は、nを返します。- 再帰呼び出しで段
n-1に到達する登り方を数えます。 - 2 回目の再帰呼び出しで段
n-2に到達する登り方を数えます。 - 2 つの数を合計して返します。
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)メモを使った再帰
考え方
再帰が遅いのは、結果を忘れてしまうからです。それぞれの個数はkだけで決まるので、ステップkの個数がわかれば、それが変わることはありません。ステップごとに1つの枠を持つ配列をメモとして用意し、各個数を最初に計算したときにその枠へ書き込みます。同じステップについて後から求めるときは、再び再帰するのではなく、その枠を読み取ります。
これで、ステップ3からステップnまでの個数はそれぞれ1回だけ、1回の加算で計算されます。n = 5の場合、呼び出しはステップ2まで1回だけ進み、その後、答えが3、5、8と戻ってきます。そしてステップ3への2回目の要求は、値を参照するだけです。これは、何十億回もの呼び出しが発生する場合と違い、O(n)時間です。
メモにはn + 1個の数値が格納され、再帰の深さは依然としてnレベルなので、空間計算量はO(n)です。枠の値が0なら、まだ計算されていないことを意味します。実際の個数はすべて少なくとも1なので、これで問題ありません。
アルゴリズム
- すべて0の、
n + 1個のスロットを持つメモを作成します。 - 再帰ヘルパーでは、
k ≤ 2の場合にkを返します。 kのメモスロットが0の場合、ヘルパーで求めたk-1とk-2の結果を足して、そのスロットに格納します。- メモスロットを返します。
nを指定してヘルパーを呼び出します。
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)2つの変数を使って下から上へ
考え方
再帰を逆向きに考えます。上から始めて下へ問いかけるのではなく、下から始めて上へ組み立てます。ステップ k の数を計算するとき、k-1 と k-2 の数はすでにわかっていて、それより前の値を再び読み取ることはありません。したがって、メモ全体を2つの変数で置き換えられます。
prev にステップ k-2 の数を、curr にステップ k-1 の数を保持します。ステップ1と2の数である prev = 1 と curr = 2 から始めます。各ステップでそれらを足して next に格納し、その後、ペアを前に進めます。n = 5 の場合、ペアは (1, 2) から (2, 3)、(3, 5)、(5, 8) と移り、curr = 8 が答えです。
ループは各回で1回加算しながら n-2 回実行されるため、時間計算量は O(n) です。また、3つの整数を保持するため、空間計算量は O(1) です。prev を上書きする前に next を計算してください。そうしないと、合計に誤った値が使われます。
アルゴリズム
n ≤ 2の場合は、nを返します。prev = 1、curr = 2を設定します。kを3からnまで変化させ、next = prev + currを計算し、その後prev = curr、curr = nextを設定します。currを返します。
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
落とし穴と境界ケース
漸化式は短いため、バグのほとんどは基底ケース、実行時間、32ビットの上限にあります。
- 単純な再帰を提出する。小さなテストには通りますが、
n = 45では約2.3 × 10^9回の呼び出しが必要になります。それぞれの個数を一度だけ保存しましょう。 - 基底ケースを間違える。2段の階段には、
1, 1と2の2通りの上り方があります。n = 2に対して1を返すと、それ以降の答えがすべてずれ、n = 3では3ではなく2が得られます。 - 並び方ではなく選択肢を数える。
1, 2と2, 1は、2通りの上り方です。2段上がる回数だけを数えるとn/2 + 1となり、n = 5では8ではなく3になります。 - ガードなしでテーブルを埋める。
n = 1の場合、n + 1 = 2個のスロットがあるテーブルでは、2段の階段の個数を格納できません。n ≤ 2なら、すぐにnを返しましょう。 - 1ステップ余分に進めてしまう。45段の場合の個数1836311903は32ビットに収まりますが、46段の場合の個数2971215073は収まりません。余分な値を計算するループは、Java、C、C#ではオーバーフローして負の数になります。
よくある質問4
階段を上る問題がフィボナッチ数列の問題であるのはなぜですか？
段数 n までの登り方は、n-1 段目から1段で進むか、n-2 段目から2段で進むかのどちらかで終わるため、ways(n) = ways(n-1) + ways(n-2) となります。これはフィボナッチの規則です。ways(1) = 1、ways(2) = 2 のとき、登り方の数は1、2、3、5、8、13と続きます。これはフィボナッチ数列を1つずらしたものです。つまり、ways(n) = F(n+1) です。
階段を上る問題の時間計算量はどれくらいですか？
ボトムアップのループはn-2回加算を行うため、O(n)時間、追加領域O(1)で実行されます。通常の再帰は指数時間です。呼び出し回数はステップごとに約1.618倍に増え、n = 45では2269806339回、つまりおよそ2.3 × 10^9回に達します。メモ化を使うと、再帰の時間計算量はO(n)、領域計算量はO(n)になります。
メモ化とボトムアップ方式の解決策の違いは何ですか？
メモ化では再帰関数を維持し、各結果を初めて計算したときにキャッシュするため、トップダウンで動作し、呼び出しスタックとテーブルが必要です。ボトムアップのループではカウントを小さい順に計算するため、必要な値はすべてすでに求められており、再帰は使いません。どちらもO(n)の処理を行います。また、ループを使えばテーブルを省き、2つの数値だけを保持できます。
1、2、または3段ずつ上る階段問題をどう解きますか？
最後の一歩で登り方を再び分けます：ways(n) = ways(n-1) + ways(n-2) + ways(n-3)。ways(0) = 1（空の登り方）、ways(1) = 1、ways(2) = 2から始め、2つではなく直近3つの個数を保持します。時間計算量は引き続きO(n)、空間計算量はO(1)です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def climbStairs(n):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 3
期待値
3