أساسيات البرمجة الديناميكية  


مستوى الصعوبة سهل
كثيرا ما يطلب في انفوسيس MAQ
البرمجة الديناميكية نظرية

في أساسيات البرمجة الديناميكية ، سنغطي أساسيات DP واختلافها عن طريقة الطمع ، فرق تسد وتكرار.

البرمجة الديناميكية هي نهج مثل العودية وفرق تسد. يقسم المشكلة إلى مشاكل فرعية. ولكن بدلاً من حل هذه المشكلات الفرعية بشكل مستقل مثل فرق تسد وتكرار ، فإنه يستخدم نتائج المشكلات الفرعية السابقة لحسابات مماثلة تُعرف أيضًا باسم مشكلة متداخلة.

يتم استخدامه لتحسين البرامج. نظرًا لأنه يستخدم النتائج المحسوبة مسبقًا ، يمكن تقليل استخدام تعقيد الوقت الأسي إلى كثير الحدود. على سبيل المثال - التعقيد الزمني للحل التكراري للأرقام القبيحة هو أسي وحل DP خطي.

بعض المشاكل الأساسية لـ DP  

  • مشكلة الأرقام القبيحة
  • تغيير العملة
  • أرقام فيبوناتشي
  • مشكلة أرقام الجرس
  • برج هانوي
  • أرقام الجرس
  • مشكلة الحقيبة

البرمجة الديناميكية (DP) مقابل الطريقة الجشعة  

في DP ، تقوم كل خطوة بتقييم الحل مع الأخذ في الاعتبار الحلول الحالية وكذلك السابقة للحصول على الحل الأمثل. ومع ذلك ، في الخوارزمية الجشعة ، نختار الخيار الأفضل مع مراعاة الوضع الحالي فقط.

على الرغم من أن الأساليب الجشعة تكون عمومًا أسرع من طريقة DP كما أنها فعالة في استخدام الذاكرة لأنها لا تخزن القيم المحسوبة مسبقًا للاستخدام المستقبلي ، إلا أنها لا تقدم ضمانًا بالحل الأمثل.

انظر أيضا
تنفيذ كومة باستخدام طابور واحد

البرمجة الديناميكية (DP) مقابل طريقة Divide & Conquer  

في لعبة فرق تسد ، نقسم المشكلة إلى مشكلات فرعية ونحل كل مشكلة فرعية بشكل مستقل. ومع ذلك ، في DP بدلاً من حل المشكلات بشكل مستقل ، نستخدم النتائج التي تم الحصول عليها مسبقًا لإجراء عمليات حسابية جديدة. بعبارة أخرى ، يمكننا أن نقول فرق تسد + Memoization = نهج ديناميكي من أعلى إلى أسفل.

(يشير Memoization إلى تقنية تخزين النتائج المحسوبة سابقًا بشكل عام في خريطة التجزئة لمنع حسابات نفس المشكلات مرارًا وتكرارًا.)

البرمجة الديناميكية (DP) مقابل طريقة العودية  

تقوم DP بتخزين الحلول المحسوبة مسبقًا لاستخدامها عند الحاجة مرة أخرى في المستقبل لتجنب إعادة الحسابات. ومع ذلك ، في العودية ، هناك إمكانية لإعادة الحسابات وهو أمر غير ضروري لأنه لا يخزن القيم.

يؤدي التكرار إلى إعادة حساب المشكلات عدة مرات ، لذلك في مثل هذه الحالات يكون التعقيد الزمني للتكرار أكبر دائمًا من حل DP.

في هذه المقالة ، غطينا حول البرمجة الديناميكية الأساسيات. في المقالات التالية ، سوف نغطي بعض المشكلات الأساسية المتعلقة بـ DP.

الرقم المرجعي اسئلة المقابلة