البرمجة الديناميكية (Dynamic Programming) هي تقنية لتحسين الخوارزميات تقوم على تقسيم المسألة المعقدة إلى مسائل فرعية متداخلة، وحل كل مسألة فرعية مرة واحدة فقط مع تخزين نتيجتها لإعادة استخدامها بدلاً من تكرار الحسابات.
متى تعرف أن المسألة تحتاج برمجة ديناميكية؟
تظهر الحاجة لهذه التقنية بوضوح عندما تجد أن الحل التكراري يعيد حساب المدخلات نفسها عشرات المرات، وتتوفر في المسألة سمتان رئيسيتان:
- البنية الفرعية المثلى (Optimal Substructure): يمكن بناء الحل الأمثل للمسألة الكبيرة انطلاقاً من الحلول المثلى لأجزائها الأصغر.
- المسائل الفرعية المتداخلة (Overlapping Subproblems): تتكرر الحسابات ذاتها عبر مسارات استدعاء مختلفة، كما في متتالية فيبوناتشي أو مسألة حقيبة الظهر (Knapsack).
الفرق بين الحفظ المؤقت (Memoization) والجدولة (Tabulation)
المقارنةالحفظ المؤقت (Top-Down)الجدولة (Bottom-Up)اتجاه التنفيذمن المسألة الكبيرة نحو الأصغرمن الحالات الأساسية نحو الهدفالآلية البرمجيةاستدعاء ذاتي مع قاموس أو مصفوفةحلقات تكرارية تملأ جدولاًخطر امتلاء المكدسمحتمل عند عمق استدعاء كبيرمنعدم تماماًسهولة الكتابةأقرب للتفكير الرياضي المباشرأكثر تحكماً في الذاكرة والأداء
قد يعجبك ايضا
تطبيق عملي: مسألة تسلق السلالم (Climbing Stairs)
إذا كان بإمكانك الصعود خطوة واحدة أو خطوتين في كل مرة، فكم طريقة للوصول إلى الدرجة رقم n؟ الحل الجدولي يختصر الزمن إلى O(n) والذاكرة إلى O(1):
def climb_stairs(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
السر في إتقان البرمجة الديناميكية ليس حفظ الحلول، بل تحديد «الحالة» (State) ومعادلة الانتقال بين الحالات قبل كتابة سطر كود واحد.
أسئلة شائعة
- السؤال: ما الفرق بين البرمجة الديناميكية وخوارزمية فرّق تسد؟ الإجابة: في «فرّق تسد» (مثل MergeSort) تكون الأجزاء مستقلة تماماً ولا تتكرر، أما في البرمجة الديناميكية فالأجزاء تتداخل وتتكرر.
- السؤال: كيف أبدأ حل مسألة DP في مقابلة عمل؟ الإجابة: اكتب الحل بالاستدعاء الذاتي أولاً، ثم أضف مصفوفة حفظ، وبعدها حوله إلى حل جدولي تكراري إن أمكن.
- السؤال: هل يمكن ضغط ذاكرة الجدول؟ الإجابة: نعم، إذا كان السطر الحالي يعتمد فقط على السطر السابق، يمكنك تقليص الذاكرة من مصفوفة ثنائية إلى أحادية أو متغيرين.
التعليقات (0)
أضف تعليقك