التخزين المؤقت والبرمجة الديناميكية
من ساعات إلى أجزاء من الثانية: احفظ ما حسبته ولا تحسبه مرتين. ⏱ نحو 40 دقيقة.
- تكتشف الحساب المكرر في الحلول العودية.
- تطبق التخزين المؤقت بقاموس وبـ
lru_cache. - تبني حلًّا بالبرمجة الديناميكية بالجدولة من الأسفل.
- تتعرف على شرطي البرمجة الديناميكية وتحل بها مسائل الدرج والقطع النقدية.
١المشكلة: نحسب الشيء نفسه مرارًا
متتالية فيبوناتشي: كل عدد مجموع العددين قبله: 0، 1، 1، 2، 3، 5، 8، 13… الحل العودي المباشر جميل، لكنه يحسب القيم نفسها مرات ومرات:
calls = 0def fib(n): global calls calls += 1 if n < 2: return n return fib(n - 1) + fib(n - 2) for n in [10, 20, 25]: calls = 0 print(n, fib(n), "| عدد الاستدعاءات:", calls)
الاستدعاءات تتضاعف تقريبًا مع كل زيادة في n: تعقيد أُسّي O(2ⁿ). fib(50) بهذه الطريقة تحتاج ساعات.
٢الحل الأول: التخزين المؤقت Memoization
الفكرة: احفظ كل نتيجة تحسبها في قاموس، وقبل أي حساب اسأل: هل حسبته من قبل؟
memo = {}calls = 0def fib(n): global calls calls += 1 if n in memo: # حُسب من قبل: O(1) return memo[n] if n < 2: result = n else: result = fib(n - 1) + fib(n - 2) memo[n] = result # احفظ للمرة القادمة return result print(fib(50), "| الاستدعاءات:", calls)
وفي بايثون يفعل ذلك سطر واحد: المزخرف @lru_cache أو @cache:
from functools import lru_cache @lru_cache(maxsize=None)def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(90))
صار كل fib(k) يُحسب مرة واحدة: O(n) زمنًا، مقابل O(n) ذاكرة للقاموس. هذه مقايضة الذاكرة بالزمن التي عرفتها في الدرس 11.
٣الحل الثاني: البرمجة الديناميكية من الأسفل
بدل العودية من الأعلى، نبني الجدول من الأصغر إلى الأكبر بحلقة. وتسمى هذه الطريقة الجدولة Tabulation، وهي قلب البرمجة الديناميكية Dynamic Programming:
def fib_table(n): table = [0, 1] for i in range(2, n + 1): table.append(table[i - 1] + table[i - 2]) return table[n] def fib_two(n): # نحتاج آخر قيمتين فقط: ذاكرة O(1) a, b = 0, 1 for _ in range(n): a, b = b, a + b return a print(fib_table(90), fib_two(90))
٤متى تنفع البرمجة الديناميكية؟
حين تحقق المسألة شرطين:
| الشرط | معناه | في فيبوناتشي |
|---|---|---|
| مسائل فرعية متداخلة | المسائل الصغيرة نفسها تتكرر. | fib(3) تُطلب من fib(4) ومن fib(5) |
| البنية المثلى | الحل الأمثل للكبيرة يُبنى من حلول الصغيرة. | fib(n) = fib(n−1) + fib(n−2) |
مثال عملي: عدد طرق صعود الدرج إن كنت تصعد درجة أو درجتين كل مرة:
def ways(n): w = [1, 1] # 0 درجات: طريقة واحدة، 1 درجة: طريقة واحدة for i in range(2, n + 1): w.append(w[i - 1] + w[i - 2]) # آخر خطوة: درجة واحدة أو درجتان return w[n] for n in [3, 5, 10, 30]: print(n, "درجات ← عدد الطرق:", ways(n))
٥مثال: أقل عدد قطع نقدية
كم أقل عدد من القطع لتكوين مبلغ معين من فئات محددة؟ نحسب لكل مبلغ من 0 إلى الهدف: أفضل حل = قطعة واحدة + أفضل حل للمبلغ الباقي:
def min_coins(coins, amount): INF = float("inf") best = [0] + [INF] * amount for x in range(1, amount + 1): for c in coins: if c <= x and best[x - c] + 1 < best[x]: best[x] = best[x - c] + 1 return best[amount] if best[amount] != INF else -1 print(min_coins([1, 5, 10, 50], 67))print(min_coins([1, 3, 4], 6)) # الجواب 2 (3 + 3)، لا 3 (4 + 1 + 1)
التعقيد O(المبلغ × عدد الفئات). وسترى في الدرس 24 أن الطريقة «الجشعة» (خذ الأكبر دائمًا) تخطئ في المثال الثاني.
توقّع وتحقّق
تعقيد فيبوناتشي العودي بلا تخزين:
حفظ نتائج الدالة لإعادة استخدامها:
بناء الجدول من الأصغر إلى الأكبر بحلقة:
شرطا البرمجة الديناميكية:
Overlapping + Optimal.الخلاصة
- فيبوناتشي الساذج
O(2ⁿ) لأنه يكرر الحسابات. - التخزين المؤقت: احفظ واسأل قبل الحساب ←
O(n)، و @lru_cacheجاهز. - الجدولة: املأ الجدول من الأصغر إلى الأكبر بحلقة.
- تنفع حين توجد مسائل فرعية متداخلة وبنية مثلى.
تحدٍّ برمجي: مسارات الشبكة
متقدمروبوت في الزاوية العليا اليسرى من شبكة 4 × 6 يتحرك يمينًا أو أسفل فقط. كم طريقًا إلى الزاوية السفلى اليمنى؟ حلها بجدول البرمجة الديناميكية.
- جدول dp بحجم الصفوف × الأعمدة.
- الصف الأول والعمود الأول: 1 (طريق واحد).
dp[r][c] = dp[r-1][c] + dp[r][c-1]- اطبع الجواب: 56
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
rows, cols = 4, 6💡 تلميح 1
r = 1 و c = 1.💡 تلميح 2
حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
rows, cols = 4, 6dp = [[1] * cols for _ in range(rows)]for r in range(1, rows): for c in range(1, cols): dp[r][c] = dp[r - 1][c] + dp[r][c - 1]print(dp[rows - 1][cols - 1])