🏃‍♂️ 階段上りDP問題の詳細解析

📋 問題概要

問題: n段の階段を、1歩でa段またはb段ずつ上る方法は何通りあるか？

例: n=11, a=3, b=4の場合

🎯 動的プログラミング（DP）の基本概念

dp[i] = dp[i-a] + dp[i-b] (i ≥ max(a,b)の場合)

💡 DPテーブルの意味

dp[i] = i段目に到達する方法の数

🔄 実例での処理過程（n=11, a=3, b=4）

ステップ1: DPテーブルの初期化

ステップ2: 段階的計算

📊 視覚的な階段表現

💻 コード解析

// 初期化フェーズ
const dp = new Array(n + 1).fill(0);  // O(n) 空間
dp[0] = 1;  // ベースケース

// 計算フェーズ
for (let i = 1; i <= n; i++) {        // O(n) 時間
    if (i >= a) dp[i] += dp[i - a];   // 状態遷移1
    if (i >= b) dp[i] += dp[i - b];   // 状態遷移2
}

⚡ 計算量解析

⏱️ 時間計算量

O(n)

各段を1回ずつ計算

💾 空間計算量

O(n)

DPテーブルのサイズ

🎮 インタラクティブデモ

異なるパラメーターでDPの動作を確認しよう！

🔍 重要なポイント

✅ なぜDPが効率的なのか？

⚠️ 注意すべきケース