今回は paiza のDPで「階段の上り方 1」の問題に挑戦！
漸化式を使うのは前回で最後じゃ無かった…。けど、図とツリー構造でわかりやすくしてみた！
問題概要
-
整数
nが与えられる。 -
n 段の階段を、1歩で 「1段」 または 「2段」 上ることができるとき、階段を上る方法は何通りあるか？
※ 1 ≦ n ≦ 40
※0段の階段を上る方法が1通り (何もしない) である
入力例：
3
出力例：
3
✅ OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const n = Number(lines[0]);
const dp = [];
dp[0] = 1;
for(let i = 1; i <= n; i++){
dp[i] = 0;
if (i === 1) dp[i] = dp[i-1];
if (i >= 2) dp[i] = dp[i-1] + dp[i-2];
}
console.log(dp[n]);
});
✅ if文による段数チェック
const dp = [];
dp[0] = 1;
for(let i = 1; i <= n; i++){
dp[i] = 0;
if (i >= 1) dp[i] = dp[i] + dp[i-1];
if (i >= 2) dp[i] = dp[i] + dp[i-2];
}
console.log(dp[n]);
「n段目にたどり着くにはどんなルートがあるのか？」
🔢 例：3段の階段（n = 3）
🔍 ゴール：3段目にたどり着く方法を数える
✅ パターン1：1段ずつ上がる
スタート → 1段 → 2段 → 3段
-
[1段ずつ ×3回]
-
経路：1 → 1 → 1
-
合計：1通り
✅ パターン2：1段 → 2段
スタート → 1段 → 3段
-
[1段 → 2段]
-
経路：1 → 2
-
合計：1通り
✅ パターン3：2段 → 1段
スタート → 2段 → 3段
-
[2段 → 1段]
-
経路：2 → 1
-
合計：1通り
🎯 結果：3通り
- 1 → 1 → 1
- 1 → 2
- 2 → 1
🔍 観点：「n段目に来るには、どこから来るのか？」
これを 木構造（ツリー状） にしてみよう！：
[3段]
↙ ↘
[2段] [1段]
↙ ↘ ↑
[1段] [0段] [0段]
- 3段に来るには、2段か1段から。
- 2段に来るには、1段か0段から。
- 1段に来るには、0段から。
これをコードで書くと以下のような再帰（漸化式）になる。
dp[n] = dp[n-1] + dp[n-2];
📌 まとめ：考え方のポイント
| ステップ | 内容 |
|---|---|
| 1 | n段目にどう来たかを考える |
| 2 | 1段前 or 2段前から来る |
| 3 | 部分問題の組み合わせになる |
| 4 | これがそのまま漸化式になる |
🎨 補助イメージ（図解）
[n]
/ \
[n-1] [n-2]
/ \ / \
... ... ... ...
- この構造はフィボナッチ数列の構造そのもの。
- 実際、0段:1通り、1段:1通り、2段:2通り、3段:3通り、… というふうに フィボナッチ数列と一致する。
「なんで dp[n] = dp[n-1] + dp[n-2] になるの？」と聞かれたら、
→「n段目に来るには、1つ前（n-1）から1段上がる or 2つ前（n-2）から2段上がるという2パターンがあるから」と言える。
📚 学習のまとめ・ポイント
- 自分で漸化式を立てる力が重要
- 「ある段にどうやって来るか？」という視点で考えると、DPの流れが自然に見える
- これは実は フィボナッチ数列と同じ構造
- 初期値
dp[0] = 1が大事（何もしないという1通り）
- if文による段数チェックは、今後の複雑な階段DPに対応する準備にもなる？
- 動的計画法（DP）の基本形。部分問題を積み上げて全体を解く。