🚀 O(1)メモリ最適化解析

階段上り問題のメモリ効率を劇的に改善する円形バッファの仕組み

⚖️ 従来法 vs 最適化法の比較

🔴 従来のDP解法

  • メモリ: O(n)
  • 配列サイズ: n+1 要素
  • n=30の場合: 31要素
  • 特徴: 全ての段の値を保持
const dp = Array(n + 1).fill(0); dp[0] = 1; for (let i = 1; i <= n; i++) { if (i>= a) dp[i] += dp[i - a]; if (i >= b) dp[i] += dp[i - b]; if (i >= c) dp[i] += dp[i - c]; }

🟢 O(1)最適化解法

  • メモリ: O(max(a,b,c))
  • 配列サイズ: M 要素
  • M=4の場合: 4要素のみ
  • 特徴: 円形バッファで必要最小限
const M = Math.max(a, b, c); const dp = Array(M).fill(0); dp[0] = 1; for (let i = 1; i <= n; i++) { let ways=0; if (i - a>= 0) ways += dp[(i - a) % M]; if (i - b >= 0) ways += dp[(i - b) % M]; if (i - c >= 0) ways += dp[(i - c) % M]; dp[i % M] = ways; }

📊 メモリ使用量の比較

従来法のメモリ使用 (n=10の場合)

dp[0]
1
dp[1]
0
dp[2]
1
dp[3]
1
dp[4]
2
dp[5]
2
dp[6]
4
dp[7]
4
dp[8]
7
dp[9]
8
dp[10]
15

メモリ使用量: 11要素 (44 bytes)

最適化法のメモリ使用 (M=4の場合)

dp[0]
動的
dp[1]
動的
dp[2]
動的
dp[3]
動的

メモリ使用量: 4要素のみ (16 bytes) - 64%削減！

🔄 円形バッファの仕組み

ステップ 1: i=1の計算

🧮 数式とアルゴリズム

円形バッファのインデックス計算:

読み取り位置: (i - step) % M
書き込み位置: i % M

状態遷移式:
dp[i % M] = dp[(i-a) % M] + dp[(i-b) % M] + dp[(i-c) % M]

📈 計算量とパフォーマンス比較

項目 従来のDP O(1)最適化DP 改善率
時間計算量 O(n) O(n) 同等
空間計算量 O(n) O(max(a,b,c)) 大幅改善
配列サイズ (n=30) 31要素 4要素 87%削減
メモリ使用量 124 bytes 16 bytes 87%削減
キャッシュ効率 中 高 向上

💡 最適化のポイント

1. 必要な情報のみ保持

DPでは現在の段 i を計算するために、i-a, i-b, i-c の値のみが必要です。 これより古い値は不要になるため、円形バッファで上書きしても問題ありません。

2. モジュロ演算による循環

i % M により配列のインデックスが循環し、M個の要素で 無限の段数に対応できます。

3. キャッシュ局所性の向上

小さな配列（4要素）はCPUキャッシュに収まりやすく、メモリアクセス速度 が向上します。

🔧 実装の詳細解析

1. 初期化
M = max(a, b, c) = 4
dp = [0, 0, 0, 0], dp[0] = 1
↓
2. ループ開始
for i = 1 to n (i = 1 to 10)
↓
3. 前の値を読み取り
ways += dp[(i-a) % M]
ways += dp[(i-b) % M]
ways += dp[(i-c) % M]
↓
4. 現在位置に書き込み
dp[i % M] = ways
↓
5. 結果取得
return dp[n % M]

📊 実際のパフォーマンス測定

0.123
処理時間 (ms)
16
メモリ使用量 (bytes)
87%
メモリ削減率
O(1)
空間計算量

🎯 この最適化の意義

大規模問題への適用可能性

アルゴリズム設計の教訓