البرمجة الديناميكية: الأمثلة والمشكلات الشائعة والحلول

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

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

ما هي البرمجة الديناميكية؟

ببساطة ، البرمجة الديناميكية هي طريقة تحسين للخوارزميات العودية ، يستخدم معظمها لحل المشكلات الحسابية أو الرياضية.

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

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

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

كبير يا، من الأسي إلى كثير الحدود.

ما هو تدوين Big-O؟

يجب أن تكون شفرتك فعالة ، ولكن كيف تُظهر مدى كفاءة شيء ما؟ مع Big-O!

الآن بعد أن أصبحت لديك فكرة جيدة عن ماهية البرمجة الديناميكية ، فقد حان الوقت للتحقق من بعض المشكلات الشائعة وحلولها.

مشاكل البرمجة الديناميكية

1. مشكلة حقيبة الظهر

عرض المشكلة

إعطاء مجموعة من العناصر ، لكل منها وزنًا وقيمة ، حدد عدد كل عنصر لتضمينه في بحيث لا يتجاوز الوزن الإجمالي حدًا معينًا وتكون القيمة الإجمالية كبيرة مثل ممكن.

يتم منحك مصفوفتين من الأعداد الصحيحة القيم [0..n-1] و الأوزان [0..n-1] التي تمثل القيم والأوزان المرتبطة بالعناصر n على التوالي. أيضا المعطى هو عدد صحيح دبليو الذي يمثل سعة الحقيبة.

نحن هنا نحل مشكلة حقيبة الظهر 0/1 ، مما يعني أنه يمكننا اختيار إما إضافة عنصر أو استبعاده.

الخوارزمية

• قم بإنشاء مصفوفة ثنائية الأبعاد باستخدام ن + 1 من الصفوف و ث + 1 الأعمدة. رقم صف ن تشير إلى مجموعة العناصر من 1 إلى أنا، ورقم العمود ث يشير إلى أقصى قدرة تحمل للكيس.
• القيمة الرقمية في [اي جاي] يشير إلى القيمة الإجمالية للعناصر حتى أنا في حقيبة يمكن أن تحمل أقصى وزن j
• في كل إحداثي [اي جاي] في المصفوفة ، اختر القيمة القصوى التي يمكننا الحصول عليها بدونها البند ط، أو القيمة القصوى التي يمكننا الحصول عليها البند طأيهما أكبر.
• الحد الأقصى للقيمة التي يمكن الحصول عليها بتضمين العنصر i هو مجموع العنصر أنا نفسها والقيمة القصوى التي يمكن الحصول عليها مع السعة المتبقية من الحقيبة.
• نفذ هذه الخطوة حتى تجد القيمة القصوى لملف دبليو^ذ صف.

رمز

def FindMax (W ، n ، القيم ، الأوزان):
MaxVals = [[0 لـ x في النطاق (W + 1)] لـ x في النطاق (n + 1)]
لأني في النطاق (ن + 1):
لـ w في النطاق (W + 1):
إذا كان i == 0 أو w == 0:
MaxVals [i] [w] = 0
أوزان elif [i-1] <= w:
MaxVals [i] [w] = أقصى (قيم [i-1]
+ MaxVals [i-1] [w-weights [i-1]] ، 
MaxVals [i-1] [w])
آخر:
MaxVals [i] [w] = MaxVals [i-1] [w]
إرجاع MaxVals [n] [W]

2. مشكلة تغيير العملة

عرض المشكلة

لنفترض أنك حصلت على مجموعة من الأرقام التي تمثل قيم كل عملة. بالنظر إلى مبلغ محدد ، أوجد الحد الأدنى لعدد العملات المطلوبة لتحقيق هذا المبلغ.

الخوارزمية

• تهيئة مصفوفة الحجم ن + 1، حيث n هي المقدار. تهيئة قيمة كل فهرس أنا في المصفوفة لتكون مساوية للمبلغ. يشير هذا إلى الحد الأقصى لعدد العملات المعدنية (باستخدام عملات معدنية من فئة 1) المطلوبة لتعويض هذا المبلغ.
• نظرًا لعدم وجود فئة لـ 0 ، قم بتهيئة الحالة الأساسية حيث مجموعة [0] = 0.
• لكل فهرس آخر أنا، نقارن القيمة فيه (التي تم ضبطها في البداية على ن + 1) بالقيمة مجموعة [i-k] +1، أين ك اقل من أنا. يتحقق هذا بشكل أساسي من المصفوفة بأكملها حتى i-1 للعثور على أقل عدد ممكن من العملات التي يمكننا استخدامها.
• إذا كانت القيمة عند أي مجموعة [i-k] + 1 أقل من القيمة الحالية عند مجموعة [i]، استبدل القيمة في مجموعة [i] مع واحد في مجموعة [i-k] +1.

رمز

def coin_change (د ، المبلغ ، ك):
أرقام = [0] * (المبلغ + 1)
لـ j في النطاق (1 ، المبلغ + 1):
الحد الأدنى = المبلغ
بالنسبة لـ i في النطاق (1 ، k + 1):
إذا (j> = d [i]):
الحد الأدنى = min (الحد الأدنى ، 1 + أرقام [j-d [i]])
الأرقام [j] = الحد الأدنى
عودة الأرقام [المبلغ]

3. فيبوناتشي

عرض المشكلة

سلسلة فيبوناتشي هي سلسلة من الأعداد الصحيحة حيث يكون العدد الصحيح التالي في السلسلة هو مجموع الرقمين السابقين.

يتم تعريفه من خلال العلاقة العودية التالية: و (0) = 0 ، و (ن) = و (ن -1) + و (ن -2)، أين و (ن) هو n^ذ مصطلح. في هذه المشكلة ، يتعين علينا إنشاء جميع الأرقام في تسلسل فيبوناتشي لأعلى حتى n^ذ مصطلح.

الخوارزمية

• أولاً ، استخدم نهجًا تعاوديًا لتنفيذ علاقة التكرار المحددة.
• حل هذه المشكلة بشكل متكرر يستلزم الانهيار و (ن) إلى و (ن -1) + ف (ن -2)، ثم استدعاء الوظيفة بـ و (ن -1) و و (ن + 2) كمعلمات. نفعل هذا حتى الحالات الأساسية حيث ن = 0، أو ن = 1 تم الوصول إليها.
• الآن ، نستخدم تقنية تسمى memoization. قم بتخزين نتائج جميع استدعاءات الوظائف في مصفوفة. سيضمن ذلك أنه لكل ن ، و (ن) يحتاج فقط إلى أن تحسب مرة واحدة.
• لأي حسابات لاحقة ، يمكن ببساطة استرداد قيمتها من المصفوفة في وقت ثابت.

رمز

مواطنه فيبوناتشي (ن): 
أرقام الألياف = [0، 1] 
بالنسبة لـ i في النطاق (2 ، n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
عودة فيب Nums [n] 

4. أطول زيادة متتالية

عرض المشكلة

أوجد طول أطول سلسلة متصاعدة متتالية داخل مصفوفة معينة. أطول اللاحقات المتزايدة هي نتيجة لاحقة داخل مجموعة من الأرقام بترتيب متزايد. يجب أن تكون الأرقام الموجودة في اللاحقة فريدة وفي ترتيب تصاعدي.

أيضًا ، لا يلزم أن تكون عناصر التسلسل متتالية.

الخوارزمية

• ابدأ بنهج تعاودي حيث تحسب قيمة أطول تتابع متزايد لـ كل صفيف فرعي ممكن من الفهرس صفر إلى الفهرس i ، حيث يكون i أصغر من أو يساوي حجم مجموعة مصفوفة.
• لتحويل هذه الطريقة إلى طريقة ديناميكية ، أنشئ مصفوفة لتخزين القيمة لكل عملية تالية. قم بتهيئة جميع قيم هذه المصفوفة بالرقم 0.
• كل فهرس أنا من هذه المصفوفة يتوافق مع طول أطول زيادة لاحقة لمصفوفة فرعية من الحجم أنا.
• الآن ، لكل مكالمة متكررة من findLIS (arr، n)، افحص ال ن^ذ فهرس المصفوفة. إذا كانت هذه القيمة 0 ، فاحسب القيمة باستخدام الطريقة في الخطوة الأولى وقم بتخزينها في ن^ذ فهرس.
• أخيرًا ، قم بإرجاع القيمة القصوى من المصفوفة. هذا هو طول أطول زيادة لاحقة لحجم معين ن.

رمز

def findLIS (myArray):
n = len (myArray)
ليس = [0] * ن
لأني في النطاق (1 ، ن):
لـ j في النطاق (0، i):
إذا كان myArray [i]> myArray [j] و lis [i] lis [i] = lis [j] +1
maxVal = 0
لأني في النطاق (ن):
maxVal = max (maxVal، lis [i])
إرجاع maxVal

حلول لمشاكل البرمجة الديناميكية

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

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

بطبيعة الحال ، فإن امتلاك الدراية بالمشاكل الشائعة لا بد أن يؤتي ثماره عندما تذهب لمقابلتك التالية. لذا افتح ملف IDE المفضلوابدأ!

أفضل 9 قنوات على طول Code على YouTube لتعلم البرمجة

هل أنت جاهز لبدء البرمجة؟ تعد قنوات YouTube هذه طريقة رائعة للبدء في تطوير الألعاب والتطبيقات والويب وغيرها من التطوير.

عن المؤلف