650. لوحة مفاتيح مكونة من 2 مفتاح

الصعوبة: متوسطة

المواضيع: الرياضيات، البرمجة الديناميكية

يوجد حرف واحد فقط "A" على شاشة المفكرة. يمكنك تنفيذ إحدى العمليتين على هذه المفكرة لكل خطوة:

• نسخ الكل: يمكنك نسخ جميع الأحرف الموجودة على الشاشة (غير مسموح بنسخة جزئية).
• لصق: يمكنك لصق الأحرف التي تم نسخها في المرة الأخيرة.

نظرًا للعدد الصحيح n، قم بإرجاع الحد الأدنى لعدد العمليات للحصول على الحرف 'A' بالضبط n مرة على الشاشة.

مثال 1:

• الإدخال: ن = 3
• الإخراج: 3
• شرح: في البداية، لدينا حرف واحد 'A'.
  • في الخطوة 1، نستخدم عملية نسخ الكل.
  • في الخطوة 2، نستخدم عملية اللصق للحصول على "AA".
  • في الخطوة 3، نستخدم عملية اللصق للحصول على "AAA".

مثال 2:

• الإدخال: ن = 1
• الإخراج: 0

مثال 3:

• الإدخال: ن = 10
• الإخراج: 7

مثال 2:

• الإدخال: ن = 24
• الإخراج: 9

قيود:

• 1

تَلمِيح:

1. كم عدد الأحرف التي قد تكون موجودة في الحافظة في الخطوة الأخيرة إذا كان n = 3؟ ن = 7؟ ن = 10؟ ن = 24؟

حل:

نحتاج إلى العثور على الحد الأدنى لعدد العمليات للحصول على n حرفًا "A" بالضبط على الشاشة. سوف نستخدم أسلوب برمجة ديناميكي لتحقيق ذلك.

1. فهم المشكلة:

   • نبدأ بحرف "A" واحد على الشاشة.
   • يمكننا إما "نسخ الكل" (الذي ينسخ محتوى الشاشة الحالي) أو "اللصق" (الذي يلصق آخر محتوى منسوخ).
   • نحتاج إلى تحديد الحد الأدنى من العمليات المطلوبة للحصول على عدد n من الأحرف "A" بالضبط على الشاشة.

2. منهج البرمجة الديناميكية:

   • استخدم مصفوفة البرمجة الديناميكية (DP) dp حيث يمثل dp[i] الحد الأدنى لعدد العمليات المطلوبة للحصول على أحرف i بالضبط على الشاشة.
   • تهيئة dp[1] = 0 نظرًا لأن الأمر يتطلب 0 عملية للحصول على حرف "A" واحد على الشاشة.
   • لكل عدد من الأحرف i من 2 إلى n، احسب الحد الأدنى من العمليات عن طريق التحقق من كل مقسوم على i. إذا كان i يقبل القسمة على d، فإن:
     • عدد العمليات اللازمة للوصول إلى i هو مجموع العمليات للوصول إلى d بالإضافة إلى العمليات المطلوبة لضرب d للحصول على i.

3. خطوات الحل:

   • تهيئة مصفوفة DP باستخدام INF (أو رقم كبير) لجميع القيم باستثناء dp[1].
   • لكل i من 2 إلى n، قم بالتكرار من خلال المقسومات المحتملة لـ i وقم بتحديث dp[i] بناءً على العمليات اللازمة للوصول إلى i عن طريق النسخ واللصق.

دعونا ننفذ هذا الحل في PHP: 650. لوحة مفاتيح ذات 2 مفاتيح

توضيح:

• التهيئة: تتم تهيئة dp برقم كبير (PHP_INT_MAX) لتمثيل حالة لا يمكن الوصول إليها في البداية.
• فحص المقسوم: لكل رقم i، تحقق من جميع المقسومات d. قم بتحديث dp[i] من خلال النظر في العمليات المطلوبة للوصول إلى d ثم الضرب للحصول على i.
• الإخراج: النتيجة هي قيمة dp[n]، والتي تعطي الحد الأدنى من العمليات المطلوبة للحصول على n حرفًا بالضبط على الشاشة.

يضمن هذا النهج حساب الحد الأدنى من العمليات بكفاءة للقيود المحددة.

روابط الاتصال

إذا وجدت هذه السلسلة مفيدة، فيرجى التفكير في منح المستودع نجمة على GitHub أو مشاركة المنشور على شبكات التواصل الاجتماعي المفضلة لديك؟. دعمكم سيعني الكثير بالنسبة لي!

إذا كنت تريد المزيد من المحتوى المفيد مثل هذا، فلا تتردد في متابعتي:

• لينكد إن
• جيثب