تفجير البالونات: البرمجة الديناميكية العكسية للفواصل

إذا أُعطيت n من البالونات ذات القيم nums، فإن تفجير البالون i يكسبكم nums[i-1] * nums[i] * nums[i+1] من العملات (حاصل ضرب قيمته وقيم جارَيه الحاليين). بعد تفجيره، يصبح الجاران متجاورين. اعثروا على الحد الأقصى من العملات التي يمكنكم جمعها بتفجير جميع البالونات. يصعب تنفيذ المحاكاة الساذجة لأن تفجير البالون يغيّر الجيران — وتتجاوز البرمجة الديناميكية العكسية على الفواصل هذه الصعوبة بأناقة.

إذا حاولنا تعريف dp[i][j] على أنه الحد الأقصى من العملات الناتجة عن تفجير البالونات في النطاق [i, j]، وفكرنا في البالون الذي ينبغي تفجيره أولًا، فسنواجه مشكلة: تفجير البالون k أولًا يعني أن nums[k-1] وnums[k+1] يجب أن يكونا الجارين الحاليين، لكن قد يجري تفجير هذين البالونين لاحقًا، ما يغيّر الجيران بصورة ديناميكية. لذلك يصعب تعريف الحالة بصورة واضحة في الاتجاه الأمامي.

تكمن الحيلة في التفكير في البالون الذي سيكون آخر بالونات التفجير في الفاصل [i, j]. عندما يكون البالون k هو الأخير الذي يُفجَّر في [i, j]، تكون جميع البالونات الأخرى في [i, j] قد اختفت مسبقًا. لذلك يكون جارَا البالون k هما بالضبط nums[i-1] وnums[j+1] — أي البالونان الحدّيان الموجودان خارج الفاصل مباشرةً. وهذا يجعل حساب عملات التفجير الأخير حتميًا؛ إذ لا يعتمد على ترتيب عمليات التفجير السابقة.

أضيفوا بالونات حارسة: أضيفوا 1 في بداية nums ونهايتها لتكوين nums = [1] + nums + [1]. عرّفوا dp[i][j] على أنه الحد الأقصى من العملات الناتجة عن تفجير جميع البالونات الموجودة strictly بين الفهرسين i وj (أي باستثناء الطرفين)، حيث يكون nums[i] وnums[j] هما البالونين الحدّيين الباقيين. العلاقة التكرارية: لكل بالون أخير مرشح k في (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

نضيف البالونات الحارسة إلى المصفوفة، ونهيّئ جدول البرمجة الديناميكية إلى الصفر (الفاصل الفارغ = 0 عملة)، ثم نملؤه بترتيب متزايد لطول الفاصل. تكون الإجابة النهائية dp[0][n+1]، وهي تمثل الحد الأقصى من العملات الناتجة عن تفجير جميع البالونات الأصلية مع بقاء البالونات الحارسة حدّين دائمين.

بالنسبة إلى [3, 1, 5, 8]، نضيف الحارسين فنحصل على [1, 3, 1, 5, 8, 1] (الفهارس من 0 إلى 5). نريد حساب dp[0][5]. بالنسبة إلى الفواصل ذات length=2 (أي التي تحتوي على بالون واحد): dp[0][2] = 1*3*1=3، وdp[1][3]=3*1*5=15، وdp[2][4]=1*5*8=40، وdp[3][5]=5*8*1=40. ومع البناء التدريجي، يكون الترتيب الأمثل هو تفجير 1 أخيرًا من بين {3,1,5,8} بعد تفجير جيرانه أولًا، لنحصل على إجمالي قدره 167 عملة.

يوجد O(n²) من الفواصل، ونجرّب لكل فاصل O(n) من نقاط التقسيم، ما يعطي تعقيدًا زمنيًا مقداره O(n³). أما المساحة فهي O(n²) لجدول البرمجة الديناميكية. عندما يكون n = 500 بالونًا، فهذا يعني 125 مليون عملية، وهو عدد قابل للتنفيذ ضمن قيود المقابلات. تبسّط إضافة البالونات الحارسة معالجة الحدود؛ فبدونها، ستحتاجون إلى فحوصات صريحة لمعرفة ما إذا كان i-1 وj+1 ضمن الحدود.

يمكن كتابة الحل نفسه بأسلوب تنازلي باستخدام @lru_cache، وقد يكون اشتقاقه أكثر بداهة أثناء المقابلة. عرّفوا solve(i, j) على أنه الحد الأقصى من العملات في الفاصل المفتوح (i, j). تجرّب الدالة كل k بوصفه التفجير الأخير، ثم تخزّن النتائج مؤقتًا. يمتلك الأسلوبان التعقيد الزمني وتعقيد المساحة نفسيهما.

من الأخطاء الشائعة تعريف dp[i][j] على أنه عدد العملات عند تفجير أول بالون في [i,j]، لا الأخير. يفشل هذا التعريف لأن حساب عملات التفجير الأول يعتمد على بالونات مجاورة لم تُفجَّر بعد، كما أن حالة هذه الجيران تتغير مع تقدم الخوارزمية. فكّروا دائمًا في العنصر الأخير عند استخدام البرمجة الديناميكية على الفواصل عندما تعتمد الحدود على العناصر المتبقية.

اختيرت قيم البالونات الحارسة لتكون 1 لأنها تعمل بوصفها عناصر محايدة في الضرب. عندما يكون بالون حدّي هو الأخير الذي يُفجَّر، تكون قيمة عملاته boundary * last * boundary = 1 * last * 1 = last. أما استخدام 0 فسيعطي 0 من العملات (وهو خطأ)، واستخدام قيم أخرى سيشوّه الحساب. توحّد حيلة البالونات الحارسة جميع حالات الحدود بصورة نظيفة، من دون معالجة خاصة للبالون الموجود في أقصى اليسار أو أقصى اليمين.

في البرمجة الديناميكية القياسية على الفواصل (مثل ضرب سلسلة المصفوفات)، تمثل نقطة التقسيم k الموضع الذي نقسم عنده المسألة إلى مسألتين فرعيتين تُحلان بصورة مستقلة. أما في مسألة Burst Balloons، فإن k هو البالون الأخير الذي يُفجَّر في الفاصل، ما يجعل الفاصلين الفرعيين [i,k] و[k,j] مستقلين، ما دام k لا يزال موجودًا بوصفه حدًا. وهذه الرؤية العكسية هي الفكرة الإبداعية التي تجعل حل مسألة تفجير البالونات ممكنًا باستخدام البرمجة الديناميكية على الفواصل.

اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.

لقد تعلّمتم في هذا الدرس: تفشل المحاكاة التقدمية لأن تفجير البالونات يغيّر الجيران بصورة غير متوقعة، وتحدّد الفكرة العكسية أن k هو البالون الأخير الذي يُفجَّر في فترة، وبذلك يصبح الجاران هما nums[i] وnums[j]، وتوفّر علاقة التكرار dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) مع إضافة قيم حارسة حلًا بزمن O(n³). بعد ذلك ننتقل إلى برمجة حقيبة الظهر الديناميكية، بدءًا من مشكلة حقيبة الظهر الكلاسيكية 0/1 وتحسين استهلاك الذاكرة فيها.