البرمجة الديناميكية — أمثلة من الحياة الواقعية

فيبوناتشي بدون DP — كارثة:
fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1) = 1
│  │  │  └─ fib(0) = 0
│  │  └─ fib(1) = 1
│  └─ fib(2) ... (يعيد الحساب!)
└─ fib(3) ... (يعيد الحساب!)

نفس القيم تحسب مرارًا → O(2ⁿ)

def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]            # 🎯 استخدم المخزّن
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

شجرة الاستدعاء بعد memoization:
fib(5)
├─ fib(4) — يُحسب ويُخزَّن
│  ├─ fib(3) — يُحسب ويُخزَّن
│  │  ├─ fib(2) — يُحسب ويُخزَّن
│  │  │  ├─ fib(1) = 1
│  │  │  └─ fib(0) = 0
│  │  └─ fib(1) = 1 ⚡ من المذكرة
│  └─ fib(2) = 1 ⚡ من المذكرة
└─ fib(3) = 2 ⚡ من المذكرة

O(n) بدلاً من O(2ⁿ) — تحسين هائل!

def fib(n):
    dp = [0, 1]          # BASE: fib(0), fib(1)
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

بناء جدول DP:

Index:  0  1  2  3  4  5
       ┌──┬──┬──┬──┬──┬──┐
       │ 0│ 1│  │  │  │  │  ← البداية
       └──┴──┴──┴──┴──┴──┘

       ┌──┬──┬──┬──┬──┬──┐
       │ 0│ 1│ 1│  │  │  │  ← dp[2] = dp[1] + dp[0]
       └──┴──┴──┴──┴──┴──┘

       ┌──┬──┬──┬──┬──┬──┐
       │ 0│ 1│ 1│ 2│ 3│ 5│  → fib(5) = 5 ✅
       └──┴──┴──┴──┴──┴──┘

جدول DP — كل خلية = أقصى قيمة لوزن معين:

         الوزن →  0    1    2    3    4
                 ┌────┬────┬────┬────┬────┐
مكبر 4kg / 3000 │  0 │  0 │  0 │  0 │3000│
                 ├────┼────┼────┼────┼────┤
لابتوب 3kg /2000 │  0 │  0 │  0 │2000│3000│
                 ├────┼────┼────┼────┼────┤
جيتار 1kg /1500 │  0 │1500│1500│2000│3500│
                 ├────┼────┼────┼────┼────┤
شاحن  1kg /1000 │  0 │1500│2500│3000│3500│
                 └────┴────┴────┴────┴────┘

def knapsack(items, capacity):
    dp = [[0] * (capacity + 1) for _ in range(len(items) + 1)]

    for i in range(1, len(items) + 1):
        weight, value = items[i - 1]
        for w in range(1, capacity + 1):
            if weight <= w:
                dp[i][w] = max(
                    dp[i - 1][w],                        # لا تأخذ
                    dp[i - 1][w - weight] + value         # خذ
                )
            else:
                dp[i][w] = dp[i - 1][w]                  # الوزن أكبر من السعة
    return dp[len(items)][capacity]

         A    C    B    D
      ┌────┬────┬────┬────┬────┐
      │  0 │  0 │  0 │  0 │  0 │
A     ├────┼────┼────┼────┼────┤
      │  0 │ 1← │ 1← │ 1← │ 1← │
B     ├────┼────┼────┼────┼────┤
      │  0 │ 1  │ 1  │ 2← │ 2← │
C     ├────┼────┼────┼────┼────┤
      │  0 │ 1  │ 2↑ │ 2  │ 2  │
D     ├────┼────┼────┼────┼────┤
      │  0 │ 1  │ 2  │ 2  │ 3↖ │
      └────┴────┴────┴────┴────┘

اتجاه الأسهم يبني السلسلة: A → B → D
LCS = "ABD"

الطريقة الغبية: جرب كل المجموعات الممكنة → 2¹⁰ = 1024 مجموعة
الطريقة الذكية (DP): ابدأ بكتاب واحد، زد تدريجياً، واحفظ أفضل نتيجة لكل وزن

تطبيقات واقعية:
💰 الاستثمار: توزيع مبلغ محدود على استثمارات مختلفة
📦 الشحن: تعبئة حاويات بأقصى قيمة
🧬 DNA: محاذاة سلاسل جينية (LCS)
🎮 الألعاب: حساب أفضل حركة (لعبة الداما)