تكرار السؤال: …
الإجابة المختصرة
تتطلب DP شرطين: مشاكل فرعية متداخلة (Overlapping Subproblems) وبنية تحتية مثالية (Optimal Substructure). Memoization نهج من الأعلى للأسفل (Top-Down مع كاش)، و Tabulation نهج من الأسفل للأعلى (Bottom-Up مع جدول).
الشرح
البنية التحتية المثالية تعني أن الحل الأمثل للمسألة الكبيرة يمكن تركيبه من الحلول المثالية للمسائل الأصغر. والمشاكل المتداخلة تعني أن نفس الحسابات تتكرر مراراً (مثل شجرة متتالية فيبوناتشي). في Top-Down Memoization، نستخدم الاستدعاء الذاتي العادي ونخزن النتيجة في Map لمنع إعادة الحساب. في Bottom-Up Tabulation، نبدأ بحل الحالات الأساسية (Base Cases) ونملأ جدول مصفوفة خطوة بخطوة، مما يوفر مساحة إطارات الـ Call Stack ويتيح تحسين استهلاك الذاكرة (Space Optimization).
مثال بالكود
// Tabulation مع تحسين الذاكرة لمسألة فيبوناتشي بزمن O(N) ومساحة O(1):
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}أخطاء شائعة
- محاولة حل مسألة باستخدام البرمجة الديناميكية بينما لا تحتوي على مشاكل فرعية متداخلة (مثل MergeSort التي تعتبر Divide and Conquer وليست DP).