八百屋のりんご購入問題 - 動的プログラミング解析

📋 問題設定

りんご2個 = 110円
りんご5個 = 200円
必要な個数 = 4個以上
制約: 2個パックまたは5個パックでしか購入できない

🧮 1. 動的プログラミング（DP）テーブルの構築過程

初期状態

DPテーブルを初期化します。dp[i] = ちょうどi個のりんごを買うのに必要な最小コスト

🎮 インタラクティブDP構築シミュレーション

ステップ 0: 初期化完了

ステップ別詳細解析

📊 2. 最終DPテーブル

🎯 3. 最小コスト探索過程

探索範囲

n=4個以上のりんごを手に入れる方法を探索

dp[4] = ∞ (4個ちょうどは作れない)
dp[5] = 200 (5個パック1つ)
dp[6] = 220 (2個パック3つ)
dp[7] = 310 (2個パック1つ + 5個パック1つ)
dp[8] = 400 (2個パック4つ)

最小値の決定

4個以上の中で最小コストを選択

min(∞, 200, 220, 310, 400) = 200円

↓

答え: 200円

⚡ 4. 計算量・メモリ効率分析

時間計算量: O(n)

DPテーブルの各要素を1回ずつ処理
各要素から2つの遷移（+2個、+5個）を実行
最終的な最小値探索もO(n)

空間計算量: O(n)

DPテーブル: (n+4+1)個の要素
追加変数: 定数個
入力サイズn≤1000なので、メモリ使用量は非常に少ない

実際の性能（n=4の場合）

メモリ使用量

DPテーブル: 9個 × 8バイト = 72バイト
変数: 約20バイト
総計: 約100バイト未満

実行ステップ数

初期化: 9ステップ
DP構築: 18ステップ（各位置から2つの遷移）
最小値探索: 5ステップ
総計: 32ステップ

🔍 5. アルゴリズムの詳細フロー

Phase 1: 初期化

dp[0] = 0 (0個なら0円)
dp[1] ~ dp[8] = ∞ (未計算)

Phase 2: DP遷移

各 i について:
• dp[i+2] = min(dp[i+2], dp[i] + a)
• dp[i+5] = min(dp[i+5], dp[i] + b)

Phase 3: 解の抽出

min(dp[n], dp[n+1], ..., dp[n+4])
ただし dp[i] ≠ ∞ のもののみ

💡 6. なぜこのアプローチが効果的なのか

🚫 単純な方法では解けない理由

2と5の最大公約数は1だが、小さな数では作れない組み合わせがある
例: 1個、3個は2個パックと5個パックでは作れない
ちょうどn個を作ろうとすると、解が存在しない場合がある

✅ DPアプローチの利点

網羅性: 全ての可能な組み合わせを効率的に探索
最適性: 各状態で最小コストを保証
柔軟性: n個以上の条件に対応可能
効率性: O(n)時間で解を求める

🍎 八百屋のりんご購入問題 - 動的プログラミング詳細解析