52. مقدمة إلى البرمجة الديناميكية (Dynamic Programming - DP)
البرمجة الديناميكية هي تقنية قوية تُستخدم في المقام الأول لمشاكل التحسين. إنها تتجنب الحسابات الزائدة عن طريق تخزين نتائج المشكلات الفرعية.
متى تكون DP قابلة للتطبيق؟
تعتبر DP مناسبة للمشاكل التي تظهر خاصيتين رئيسيتين:
- البنية المثلى (Optimal Substructure): يمكن بناء حل أمثل للمشكلة من حلول مثلى لمشكلاتها الفرعية (مماثلة لـ Greedy/D&C).
- المشكلات الفرعية المتداخلة (Overlapping Subproblems): يتم حل نفس المشكلات الفرعية بشكل متكرر بواسطة خوارزمية عودية. هذا التكرار هو ما تستهدفه DP.
DP مقابل القسِّم تسُد (Divide and Conquer)
- D&C: المشكلات الفرعية مستقلة (على سبيل المثال، فرز الجانب الأيسر من Merge Sort لا يؤثر على فرز الجانب الأيمن).
- DP: المشكلات الفرعية مترابطة ومتداخلة (على سبيل المثال، يتطلب حساب Fibonacci(5) حساب Fibonacci(4) و Fibonacci(3). ويتطلب حساب Fibonacci(4) أيضاً حساب Fibonacci(3)).