إخلاء المسؤولية: الطريقة الموضحة أدناه ليست عالمية ، لكنها غالبًا ما تحل مشكلة أو تساعدك في الوصول إلى الحل الصحيح.
إذا كانت المشكلة تتلخص في حقيقة أنه من الضروري تقسيم المصفوفة إلى أجزاء فرعية غير متقاطعة (سلسلة من العناصر المتتالية) بالطريقة المثلى (أو حساب عدد الانقسامات المناسبة) ، فإن الأمر يستحق محاولة حلها باستخدام البرمجة الديناميكية.
مثال على مخطط الحل هو كما يلي:
dp [i] - استجابة لعناصر i الأولى
حساب dp [i]: نظرًا لأننا ندرس فقط عناصر i الأولى ، سيكون العنصر i هو العنصر الأخير ، مما يعني أن هذا العنصر سيكون في آخر جزء فرعي ، وفي نفس الوقت ، سيكون العنصر الموجود في أقصى اليمين هناك. لذلك ، يمكننا التكرار فوق الحد الأيسر للجزء الفرعي الأخير j. في عملية العد ، سنحسب قيمة هذه القطعة الفرعية ، وإذا كانت صحيحة ، فسنقوم بإعادة حساب dp [i] من خلال dp [j - 1] وقيمة القطعة الفرعية [j ؛ i].
ضع في اعتبارك المشكلة البسيطة التالية: بالنظر إلى مصفوفة من الأعداد الصحيحة ، تحتاج إلى تقسيمها إلى الحد الأدنى لعدد الأجزاء الفرعية غير المتقاطعة بحيث يتم تضمين كل رقم في بعض الأجزاء الفرعية وأن يحتوي كل جزء فرعي على نفس الأرقام. على سبيل المثال ، بالنسبة لمصفوفة 1 2 2 3 3 3 2 1 1 ، يبدو القسم الأمثل كما يلي: [1] [2 2] [3 3 3] [2] [1 1]. يمكن حل هذه المهمة بسهولة عن طريق المرور ببساطة عبر المصفوفة (نضع كل العناصر المتتالية نفسها في جزء فرعي واحد) ، لكننا سنحلها باستخدام البرمجة الديناميكية كمثال.
نبسب ؛
إنتن.
سينما & GT ؛ & GT. ن؛
// ملء المصفوفة بـ 1-index
متجه arr (n + 1) ؛
لـ (int i = 1 ؛ i & lt ؛ = n ؛ i ++)
سينما & GT ؛ & GT. arr [i] ؛
// في البداية عيّن + oo لقيم dp
متجه dp (n + 1 ، 1000000000) ؛
// لا يلزم تقسيم مصفوفة طولها صفر ، لذا فإن الإجابة عليها هي 0
موانئ دبي [0] = 0 ،
// عد إجابة dp [i] تصاعديًا i
لـ (int i = 1؛ i & lt؛ = n؛ i ++) {
// حاليًا يعد arr [i] العنصر الأخير ، لذلك سيكون الرقم الموجود في أقصى اليمين في المقطع الفرعي الأخير
// حلقة من خلال جميع الخيارات الخاصة بمكان بدء هذا الجزء الفرعي الأخير
لـ (int j = i؛ j & gt؛ 0؛ j--) {
إذا (arr [j]! = arr [i]) {
// إذا قابلت عنصرًا لا يساوي العنصر الأخير ، فستحتوي القطعة الفرعية على أرقام مختلفة ، وهذا لا يتناسب مع الشرط
// لا جدوى من الاستمرار لأن نقل الحد الأيسر إلى اليسار ، لن يختفي هذا العنصر ، لذا فإننا ننكسر
استراحة؛
}
// تخيل أن آخر جزء فرعي كان [j ؛ i]
// لذلك تحتاج إلى أخذ القسم الأمثل لعناصر j-1 الأولى وإضافة 1 (الجزء الفرعي [j ؛ i] نفسه)
dp [i] = min (dp [i]، dp [j - 1] + 1) ؛
}
}
كوت & lt؛ & lt؛ موانئ دبي [ن] ؛
إذا كانت العناصر قد لا تنتمي إلى أي من الأقسام الفرعية ، فأنت تحتاج فقط إلى التفكير في الخيار المناسب ، مثل dp [i] = dp [i - 1]