階段の上り方を数える｜コーディング面接問題

問題

n 段の階段を、1 回に 1 段か 2 段ずつ上ります。いちばん上まで上る上り方が何通りあるかを返す関数を書いてください。

上る順が違えば、別の上り方として数えます。たとえば「1 段、2 段」と「2 段、1 段」は別です
n は 1 以上 45 以下の整数です

入力と出力の例

例 1

「1、1、1、1」「1、1、2」「1、2、1」「2、1、1」「2、2」の 5 通りです。

入力

n = 4

出力

例 2

入力

n = 5

出力

例 3

1 段だけなら、1 段上る 1 通りです。

入力

n = 1

出力

面接での聞かれ方

面接では、次のように渡されることが多いです。

「階段を 1 段か 2 段ずつ上ります。n 段の上り方は何通りですか」
再帰で書くと「n が 45 だと、どのくらい時間がかかりますか？」と続けて聞かれます
「1 回に 3 段まで上れるとしたら？」と、決まりを変えて聞かれることもあります

数え方を決める前に、小さな n を手で数えて、答えの並びを先に見ておくと、決まりに気づきやすくなります。

まず考える手順

段 1

最後の 1 回に目を向けます。いちばん上へ着く直前は、1 つ下の段から 1 段上ったか、2 つ下の段から 2 段上ったかのどちらかです。なので「n 段の上り方」は「n - 1 段の上り方」と「n - 2 段の上り方」を足した数になります。これをそのまま再帰で書けば、正しい答えが出ます。

段 2

素直な再帰は遅くなります。n 段を求めるのに n - 1 段と n - 2 段を呼び、n - 1 段がまた n - 2 段を呼ぶので、同じ段の計算が何度も繰り返されます。呼び出しの数は n が 1 増えるごとに約 1.6 倍に増え、n が 45 だと 10 億回を超えます。

段 3

一度求めた段の答えを、辞書に覚えておきます。同じ段がまた呼ばれたら、計算せずに覚えた答えを返します。こうすると、どの段も 1 回しか計算しないので、呼び出しは n に比例する数で済みます。

段 4

再帰をやめて、下から表を積み上げることもできます。1 段は 1 通り、2 段は 2 通りから始め、3 段、4 段と前の 2 つを足して表を埋めます。上から呼ぶ代わりに、小さい段から順に答えを決めていく形です。

段 5

表をよく見ると、次の段を求めるのに使うのは、すぐ前の 2 つだけです。なので表全体を持たず、2 つの変数だけを持ち歩けば足ります。解答はこの形で書きます。

ここから解答です。先に自分で書いてから読むと、考え方が残ります。

解答

Python

def climb_ways(n):
    prev, cur = 1, 1
    for _ in range(n - 1):
        nxt = prev + cur
        prev = cur
        cur = nxt
    return cur

JavaScript

function climbWays(n) {
  let prev = 1;
  let cur = 1;
  for (let i = 2; i <= n; i++) {
    const next = prev + cur;
    prev = cur;
    cur = next;
  }
  return cur;
}

始めの prev は「0 段の上り方」で、何もしない 1 通りと数えています。こう置くと、2 段の答えが 1 と 1 を足した 2 になり、そのまま決まりどおりに進められます。

計算量

時間は O(n) です。1 段から n 段まで、1 回ずつ足し算をします
使う記憶は O(1) です。持つのは 2 つの変数だけです
段 3 の覚えておく再帰と段 4 の表は、時間は同じ O(n) で、記憶は O(n) です。段 1 の素直な再帰は、時間が n に対して指数的に増えます

よくある間違い

素直な再帰のまま出す。小さな n では正しく速く見えるので、遅さに気づきにくいです。n が 30 を超えたあたりから目に見えて遅くなります
始めの値を取り違える。 1 段を 1 通り、2 段を 2 通りとしたうえで、ループの回数を 1 回ずらすと答えが 1 つ隣の数になります。小さな n を 2、3 個手で確かめてから回数を決めます
大きな数があふれる言語を見落とす。 n が 45 のとき答えは約 18 億で、32 ビットの整数の上限に近いです。Python と JavaScript では問題ありませんが、ほかの言語で書くなら型の大きさを確かめます

面接での話し方の例

書き始める前に、方針を短く口に出します。

「最後の 1 回は 1 段か 2 段なので、n 段の上り方は n - 1 段と n - 2 段の上り方を足した数です。そのまま再帰で書くと同じ計算を繰り返して遅いので、小さい段から順に答えを積み上げます。使うのは前の 2 つだけなので、変数 2 つで足ります。時間は O(n)、記憶は O(1) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の n が 5 でたどります。0 段と 1 段を 1 通りずつとして始め、2 段は 2、3 段は 3、4 段は 5、5 段は 3 と 5 を足して 8 です。例 1 の 4 段が 5 になっていることも、途中で確かめられます。」

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026年10月24日