動的計画法 (DP) で階段の上り方を数える

動的計画法 (DP)問題 66

1 段か 2 段ずつ上るとき、n 段の階段の上り方が何通りあるかを数える。小さな段の答えを覚えて使い回す、動的計画の最初の練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

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 を手で数えて、答えの並びを先に見ておくと、決まりに気づきやすくなります。

ヒント

まだ開いていません

付箋は 5 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4
ヒント 5答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 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;
}

Go

func climbWays(n int) int {
	prev, cur := 1, 1
	for i := 2; i <= n; i++ {
		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 では問題ありませんが、ほかの言語で書くなら型の大きさを確かめます

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

main.py

def climb_ways(n: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(climb_ways(4))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します