階段の登り方
階段の登り方
このレッスンで分かること
- 漸化式さえ立てられれば、あとはボトムアップで配列を埋めるだけ
- 動的計画法の入門で最も有名な問題が 階段の登り方 です
- この問題が大事な理由は、
動的計画法の本質である「部分問題への分解」を体感できることにあります
階段の登り方 とは
1段または2段ずつ登れる階段の登り方の総数を DP で数える。漸化式の発見と基底ケースの設定を体得する。
動的計画法の入門で最も有名な問題が 階段の登り方 です。n 段の階段があり、1 ステップで 1 段 か 2 段 を登れる。何通りの登り方があるか? という問題です。答えは実はフィボナッチ数列そのものなのですが、自力で漸化式を導けるようになるのが目標です。
この問題が大事な理由は、動的計画法 の本質である「部分問題への分解」を体感できることにあります。n 段目に到達する方法は、n-1 段目から 1 段登るか、n-2 段目から 2 段登るか、その 2 つしかありません。この 再帰的な構造 を見抜けるかどうかが DP の入り口です。
「n 段目にたどり着く方法は、最後の 1 歩で 1 段か 2 段か」と分けて考える。これが DP の発想。
漸化式を導く
f(n) を「n 段の階段の登り方の総数」と定義します。最後の 1 歩に着目すると次のように場合分けできます。
- 最後に 1 段登った場合、その直前は
n-1段目にいた。そこまでの登り方はf(n-1)通り。 - 最後に 2 段登った場合、その直前は
n-2段目にいた。そこまでの登り方はf(n-2)通り。
これら 2 つは 重複しない ので、足し合わせて f(n) = f(n-1) + f(n-2) となります。基底ケースは f(1) = 1、f(2) = 2 です (f(0) = 1 と定義することも多いです)。
図のポイント (テキスト併記)
- 図にすると、
f(n)がf(n-1)とf(n-2)の和になる構造がはっきり見えます
図にすると、f(n) が f(n-1) と f(n-2) の和になる構造がはっきり見えます。フィボナッチ数列と全く同じ漸化式です。
漸化式さえ立てられれば、あとはボトムアップで配列を埋めるだけ。これが DP の典型パターン。
Python での実装
Python
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]n <= 2 の特例を先に処理し、それ以外はサイズ n+1 の配列を埋めていきます。インデックスは 1 始まりにすると意味と一致して読みやすいです。
JavaScript での実装
JavaScript
function climbStairs(n) {
if (n <= 2) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}発想は Python とまったく同じ。new Array(n + 1).fill(0) で初期化してから for ループで埋めるのも変わりません。dp[0] の値は本問題では使われないので、初期化のままの 0 で問題ありません。
フィボナッチとの関係
この問題の答えは実は フィボナッチ数列 に一致します。climbStairs(n) = Fib(n + 1) という関係があり、Fib(1) = 1、Fib(2) = 1、Fib(3) = 2、Fib(4) = 3、Fib(5) = 5 … と続くので、climbStairs(1) = 1、climbStairs(2) = 2、climbStairs(3) = 3、climbStairs(4) = 5 と並びます。漸化式が同じ形なのだから当然ですが、登り方の総数 と 数列の値 という、見た目がまったく違う問題が 同じ漸化式 で表現されるのは DP の面白いところです。
異なる問題が 同じ漸化式 に帰着することはよくある。一度どこかで見た式は、別の文脈でも応用できないか考えると視野が広がる。
よくある間違い
1 つ目は 基底ケース の取り違え。f(1) = 1、f(2) = 2 ですが、f(0) を 0 にすると上の漸化式が崩れます。f(0) = 1 (空の登り方 1 通り) と定義するか、n <= 2 を特例として早期 return するのが安全です。2 つ目は 配列のオフバイワン。サイズが n+1 でないとループの最後でインデックスエラーになります。3 つ目は 掛け算と勘違い。f(n) は「n-1 段までの登り方 × 1 段ぶん」ではなく、f(n-1) 通りそれぞれに最後の 1 歩を足すだけなので、掛け算ではなく足し算 です。
やってみよう
1 段か 2 段ではなく1 段か 2 段か 3 段登れる場合の漸化式を考える。f(n) = f(n-1) + f(n-2) + f(n-3)になる。dp配列を出力して、各段までの登り方が表のように積み上がるのを確認する。- 変数 2 つに圧縮した版を書き直し、メモリ
O(1)版を作ってみる。
階段の登り方を DP で解けたなら、フィボナッチ系 DP は卒業。次は コイン両替 など、より自由な遷移パターンの DP に進める。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は コイン両替最小枚数 で、複数種類のコインで目標金額を作る最小枚数を DP で求める方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 階段の登り方 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 階段の登り方 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- f(1) = 1、f(2) = 2 を基底ケースにする
- f(n) = f(n-1) + f(n-2) の漸化式に従って DP 配列を埋める
- 再帰の代わりにループで実装し、n >= 30 でも一瞬で返ること
入出力例
test-cases.txt
climbStairs(1) → 1
climbStairs(2) → 2
climbStairs(3) → 3
climbStairs(4) → 5
climbStairs(5) → 8
climbStairs(10) → 89
climbStairs(20) → 10946