今回は paiza のDPで「階段の上り方 2」の問題に挑戦！
前回の問題が理解できているかが試される！
問題概要
段数が n の階段を、1歩で a 段 または b 段 上れるときの、ちょうど n 段に到達する方法の総数を求める。
◯入力
n a b
- 1 ≤ n ≤ 40
- 1 ≤ a ≤ 5
- 1 ≤ b ≤ 5
- a ≠ b
◯出力
方法の数
◯注意点
- 到達不可能な場合は答えは 0 になる
- 0段からスタート（最初は「何もしていない状態」で方法数は1通り）
入力例:
11 3 4
出力例:
3
✅ OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = [];
dp[0] = 1;
for(let i = 1; i <= n; i++){
dp[i] = 0;
if (i >= a) dp[i] = dp[i] + (dp[i-a] || 0);
if (i >= b) dp[i] = dp[i] + (dp[i-b] || 0);
}
console.log(dp[n]);
});
🔍 視覚化解説！
木構造 と dp表の流れ の両方で、n=11, a=3, b=4 の例を視覚化する！
1️⃣ 木構造での視覚化（ルート探索）
ルートは「0段からスタートして n=11 段にたどり着く道」を表す。
今回は "+3段" or "+4段" しかできない。
(0段)
├─ +3 → (3段)
│ ├─ +3 → (6段)
│ │ ├─ +3 → (9段)
│ │ │ ├─ +3 → (12段) ❌ オーバー
│ │ │ └─ +4 → (13) ❌
│ │ └─ +4 → (10)
│ │ ├─ +3 → (13) ❌
│ │ └─ +4 → (14) ❌
│ └─ +4 → (7)
│ ├─ +3 → (10) → ... ❌ 同上
│ └─ +4 → (11) ✅ ゴール
└─ +4 → (4)
├─ +3 → (7)
│ ├─ +3 → (10) ❌
│ └─ +4 → (11) ✅ ゴール
└─ +4 → (8)
├─ +3 → (11) ✅ ゴール
└─ +4 → (12) ❌
✅ ゴールに到達するルート：
- 0 → 3 → 7 → 11 (+3 +4 +4)
- 0 → 4 → 7 → 11 (+4 +3 +4)
- 0 → 4 → 8 → 11 (+4 +3 +3)
2️⃣ DP表の流れ
dp[i] = 「i段目にたどり着く方法の数」- 初期条件：
dp[0] = 1（何もしない1通り）
i dp[i] 計算根拠
0 1 初期条件
1 0 a=3, b=4では到達不可
2 0 同上
3 1 dp[0]から+3
4 1 dp[0]から+4
5 0 到達不可
6 1 dp[3]から+3
7 2 dp[3]から+4 + dp[4]から+3 → 1+1=2
8 1 dp[4]から+4
9 0 到達不可
10 1 dp[7]から+3
11 3 dp[7]から+4 + dp[8]から+3 → 2+1=3
| i | dp[i] | 計算根拠 |
|---|---|---|
| 0 | 1 | 初期条件 |
| 1 | 0 | a=3, b=4では到達不可 |
| 2 | 0 | 同上 |
| 3 | 1 | dp[0]から+3 |
| 4 | 1 | dp[0]から+4 |
| 5 | 0 | 到達不可 |
| 6 | 1 | dp[3]から+3 |
| 7 | 2 | dp[3]から+4 + dp[4]から+3 → 1+1=2 |
| 8 | 1 | dp[4]から+4 |
| 9 | 0 | 到達不可 |
| 10 | 1 | dp[7]から+3 |
| 11 | 3 | dp[7]から+4 + dp[8]から+3 → 2+1=3 |
最終的に dp[11] = 3 となり、木構造のルート数と一致。
こうすると、
- 木構造 → ルートの分岐が見える
- DP表 → 実際のカウントの流れが見える
で、両方から同じ答え「3」が導かれるのがわかる！
📚 学習のまとめ
- 考え方は前問の階段問題と同じ
- 「
n段目にたどり着く前の状態」を考える - 前の状態は
n-a段目 またはn-b段目
- 「
- 漸化式
dp[i] = 0
if i >= a → dp[i] += dp[i-a]
if i >= b → dp[i] += dp[i-b]
- 初期条件
-
dp[0] = 1（何もしない1通り）
-
- 答え
-
dp[n]が最終的な方法の数
-
- ポイント
- a,bが3,4のように「全段に到達できない」場合もある
- 木構造でルートを視覚化するとイメージしやすい
- DP表で計算を追うと、重複カウントを防ぎつつ正確に求められる