🪜 階段上り問題の動的プログラミング解析
📊 問題設定
入力例: n=10, a=2, b=3, c=4
目標:
10段の階段を1歩で2段、3段、または4段ずつ上って到達する方法の数を求める
🧮 DPテーブルの初期化と計算過程
リセット
前のステップ
次のステップ
自動再生
🏗️ 階段の可視化
各段から可能なジャンプ:
+2段 ,
+3段 ,
+4段
📍 10段目への到達パターン例
2段ジャンプで到達:
0
→
2
→
4
→
6
→
8
→
10
3段ジャンプ組み合わせ:
0
→
3
→
6
→
9
→
10 (+1は不可)
4段ジャンプ組み合わせ:
0
→
4
→
8
→
10 (+2)
混合パターン:
0
→
2 (+2)
→
5 (+3)
→
9 (+4)
→
10 (+1は不可)
📈 状態遷移の数式
dp[i] = dp[i-a] + dp[i-b] + dp[i-c]
具体的な計算例 (i=10の場合):
dp[10] = dp[8] + dp[7] + dp[6]
dp[8] = 5 (8段目から2段ジャンプ)
dp[7] = 4 (7段目から3段ジャンプ)
dp[6] = 8 (6段目から4段ジャンプ)
結果: dp[10] = 5 + 4 + 8 = 17
⚡ 計算量解析
時間計算量
O(n)
1から n まで各段を1回ずつ計算
各段で定数時間の処理（3つの加算）
合計: n × O(1) = O(n)
空間計算量
O(n)
DPテーブル: 配列サイズ n+1
その他の変数: 定数個
合計: O(n) + O(1) = O(n)
💡 アルゴリズムの詳細分析
1. 初期化フェーズ
const dp = new Array(n + 1).fill(0); dp[0] = 1; // ベースケース:
スタート地点への到達方法は1通り
2. 状態遷移フェーズ
for (let i = 1; i <= n; i++) { if (i>= a) dp[i] += dp[i - a]; // a段前から来る if (i
>= b) dp[i] += dp[i - b]; // b段前から来る if (i >= c) dp[i] += dp[i - c]; //
c段前から来る }
3. メモ化の効果
なぜDPが効率的か:
重複する部分問題 : dp[i]は複数のdp[j] (j >
i)から参照される
最適部分構造 : dp[i]の最適解は dp[i-a],
dp[i-b], dp[i-c] の最適解から構築
ボトムアップ方式 :
小さい問題から順に解いて大きい問題を解決
🔄 再帰との比較
再帰解法の問題点:
時間計算量: O(3^n) - 指数的増加同じ計算の繰り返し: dp[i]が何度も計算されるスタックオーバーフロー: nが大きいときに発生する可能性
DP解法の利点:
時間計算量: O(n) - 線形時間各計算を1回のみ: メモ化により効率的安定性: ループ処理でスタック問題なし