Burst Balloons
يُعطى صف من البالونات على هيئة nums، حيث nums[i] هو الرقم الموجود على البالون i. تفجّرها جميعًا، واحدًا تلو الآخر، بأي ترتيب. يمنحك تفجير بالون left × nums[i] × right من العملات، حيث left وright هما الرقمان الموجودان على جارَيْه الحاليين، أي أقرب بالون على كل جانب ما زال في الصف. يُحسب الجار المفقود على أنه 1. بعد تفجير بالون، يصبح جاراه متجاورين. أعد أكبر عدد من العملات يمكنك جمعه.
الدالة
- numsinteger-array
- الأرقام على البالونات، من اليسار إلى اليمين
- تُرجعinteger
- أكبر عدد من العملات التي يمكنك جمعها عن طريق تفجير كل بالون
القيود
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- الإجابة أقل من 3 × 108، لذا فهي تلائم عددًا صحيحًا موقّعًا من 32 بت.
أمثلة
- المدخلات
- nums = [2, 4, 3]
- المخرجات
- 33
- الشرح
- فجّر الرقم 4 لتحصل على 2 × 4 × 3 = 24. الرقم 2، الموجود الآن بجانب الرقم 3، يساوي 1 × 2 × 3 = 6، والرقم 3 يساوي 3: المجموع 33.
- المدخلات
- nums = [6, 1, 2, 5]
- المخرجات
- 108
- الشرح
- فجّر الـ 1 (6 × 1 × 2 = 12)، ثم الـ 2، والآن بين 6 و5 (6 × 2 × 5 = 60)، ثم الـ 5 للحصول على 30 والـ 6 للحصول على 6: المجموع 108.
- المدخلات
- nums = [8]
- المخرجات
- 8
- الشرح
- لا يجاور البالون الوحيد أي بالونات، ويُحتسب كل جار مفقود بمقدار 1، لذا تكون نتيجته 1 × 8 × 1 = 8.
سؤال إضافي
هل يمكنك أيضًا إرجاع ترتيب واحد يحقق أكبر عدد من العملات؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لنفترض أنك قررت أي بالون ستفرقع أولًا. يصبح جارا هذا البالون متجاورين، لذا تظل البالونات الموجودة على يساره والبالونات الموجودة على يمينه تؤثر بعضها في بعض. هل يمكنك تقسيم المسألة بهذه الطريقة إلى مسألتين أصغر؟
اعكس السؤال واختر البالون الذي ينفجر أخيرًا في مقطع. حتى ذلك الحين يظل ثابتًا كالجدار، لذا لا يصبح البالونان الواقعان على يساره ويمينه متجاورين أبدًا. وعندما ينفجر أخيرًا، يكون جاراه هما البالونين اللذين يحدّان المقطع.
ضع العدد 1 عند طرفي
nums. لتكنbest[left][right]أكبر عدد من العملات التي يمكن جمعها من البالونات الواقعة حصريًا بين الموضعينleftوright. جرّب كل بالونkبينهما بوصفه الأخير: يكسبbest[left][k] + best[k][right]بالإضافة إلىvals[left] × vals[k] × vals[right]. املأ الفجوات القصيرة قبل الطويلة.
الحل
تُغيّر كل عملية تفجير مَن يجاور مَن، لذا فإن أول بالون تفجّره لا يقسم الصف: إذ يصبح الجانبان متجاورين. أمّا آخر بالون يُفجَّر ضمن مقطع، فهو الذي يقسمه. إذ يبقى في مكانه بينما يزول كل ما عداه، وتصبح المقاطع على جانبيه مستقلة، لذا يحل جدول الفواصل على المقاطع المسألة في O(n³).
جرّب كل ترتيب للتفجير
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اختر بالونًا، واجمع left × value × right، وأزِله، ثم حلّ الصف الأقصر بالطريقة نفسها، مع الاحتفاظ بأفضل مجموع عبر جميع الخيارات. يجرّب كل الترتيبات، لذا فهو صحيح.
للانفجار الأول n خيارات، وللذي يليه n-1، وهكذا: هناك n! ترتيبًا، ويبلغ عددها بالفعل 479,001,600 عند وجود 12 بالونًا. لا يفيد تذكّر النتائج لكل مجموعة من البالونات المتبقية، لأن عدد المجموعات هو 2^n.
الخوارزمية
- اكتب
burstAll(row)، لإيجاد أكبر عدد من العملات من البالونات فيrow، و0 إذا كان الصف فارغًا. - لكل موضع
k، اكسبleft × row[k] × right، باستخدام 1 بعد أيٍّ من الطرفين، بالإضافة إلىburstAllللصف من دونrow[k]. - أعِد أفضل مجموع على جميع قيم
k، واستدعِburstAll(nums).
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)الاستدعاء الذاتي للبالون الأخير، مع مذكرة
الفكرة
أضف 1 إلى الصف عند كل طرف: vals = [1] + nums + [1]. لا تنفجر القيم المضافة، وهي تحل محل الجارين المفقودين. لتكن solve(left, right) أكبر عدد من العملات التي يمكن جمعها من البالونات الواقعة تمامًا بين موضعين ثابتين.
لنفترض أن k هو آخر بالون ينفجر في تلك الفجوة. تنفجر جميع البالونات الأخرى فيها بينما يبقى k كالجدار، لذا لا يرى الجزء بين left وk سوى بالوناته وحدوده الثابتة، وينطبق الأمر نفسه على الجزء بين k وright. عندما ينفجر k، يكون جاراه بالضبط left وright. لذا فإن أفضل نتيجة للفجوة هي، عبر جميع قيم k، أفضل مجموع للجزأين مضافًا إليه vals[left] × vals[k] × vals[right]. الإجابة هي نتيجة الفجوة بين الحشوتين. هناك نحو n²/2 فجوة، وتجرب كل منها ما يصل إلى n بالونات، لذا تجعل المذكرة الزمن O(n³).
الخوارزمية
- أنشئ
valsباعتبارهاnumsمع إضافة 1 إلى كل طرف، واجعلmيساوي طولها. - أنشئ مصفوفة تذكّر
m × mمملوءة بـ -1. - اكتب
solve(left, right): أعد 0 إذا كانright - left < 2، وأعد القيمة المخزنة إن وُجدت. - وإلا، جرّب كل
kيقع بينهما تمامًا بوصفه البالون الأخير، واحتفظ بأكبر قيمة لـsolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]، ثم خزّنها. - أعد
solve(0, m-1).
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)املأ جدول الفترات حسب العرض
الفكرة
لا يسأل الاستدعاء الذاتي إلا عن فجوات أضيق، لذا املأ الجدول نفسه باستخدام الحلقات، بدءًا بالفجوات الضيقة قبل الواسعة. عندئذٍ تكون best[left][k] وbest[k][right] قد حُسبتا نهائيًا كلما احتاجت إليهما فجوة أوسع.
بالنسبة إلى [2, 4, 3]، بعد إضافة حارسين لتصبح [1, 2, 4, 3, 1]، تجرّب best[0][4] كل بالون باعتباره الأخير. إذا كان 3 هو الأخير، فالناتج هو best[0][3] = 30 زائد 1 × 3 × 1، أي 33، وهو الأفضل من بين الاحتمالات الثلاثة.
يتطابق مقدار العمل مع نسخة التخزين المؤقت، لكن الحلقات العادية تتجاوز ملايين استدعاءات الدوال، ما يجعل هذه النسخة أسرع بعدة مرات في لغة مثل Python أو R.
الخوارزمية
- أنشئ
valsباعتبارهاnumsمع إضافة 1 عند كل طرف، واجعلmيساوي طولها. - أنشئ جدولًا بحجم
m × mاسمهbest، واملأه بالأصفار. - لكل عرض من 2 إلى
m-1، ولكلleftبحيث يكونright = left + widthداخل المصفوفة، جرّب كلkيقع بينهما تمامًا. - اجعل قيمة
best[left][right]أكبر قيمة بينbest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - أعِد
best[0][m-1].
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
أخطاء شائعة وحالات حدّية
- التقسيم عند أول بالون يُفقَع مع جيرانه الأصليين،
nums[k-1] × nums[k] × nums[k+1]بالإضافة إلى الجانبين. قد يكون هذان الجاران قد اختفيا بالفعل: في[2, 4, 3]يعطي الناتج 44، وهي قيمة أكبر مما تحققه أي عملية فقع فعلية. - ملء الجدول صفًا بعد صف مع زيادة
left. عندها لا تكونbest[k][right]محسوبة بعد عندما يكونk > left، فتُقرأ على أنها 0. املأ الجدول حسب العرض، أو مرّر علىleftتنازليًا. - تعيين 0 لفجوة لم تُحلّ في الذاكرة المؤقتة. فالفجوة التي تحتوي على بالونات قيمتها صفر تساوي قيمتها فعلًا 0، لذا يُعاد حلّها عند كل زيارة. استخدم -1.
- في Lua وR، تمتد المواضع المضافة من 1 إلى
m، لذا تكون الإجابةbest[1][m].
أسئلة شائعة3
لماذا تختار مسألة «تفجير البالونات» البالون الأخير بدلًا من الأول؟
بعد الانفجار الأول، يصبح جانباها متجاورين، لذا يظل كلٌّ منهما يؤثر في الآخر. يبقى البالون الأخير في مقطعٍ ما حتى تنفجر البالونات الأخرى، لذا لا يلتقي جانباه أبدًا، ويكون كل جانب مسألة فرعية مستقلة. وعندما ينفجر، يكون البالونان المجاوران له حدَّي المقطع.
ما هو التعقيد الزمني لمسألة تفجير البالونات؟
زمن O(n³) وذاكرة O(n²): نحو n²/2 من الفجوات، تحاول كل منها ما يصل إلى n بالونًا بوصفه الأخير. بالنسبة إلى 300 بالون، يعادل ذلك نحو 4.5 × 10^6 خطوة. تجربة كل ترتيب تستغرق O(n · n!).
هل يمكن حل مسألة تفجير البالونات بترتيب جشع؟
لا. إن تفجير أصغر بالون أولًا يحقق 24 على [2, 4, 3]، بينما يمكن تحقيق 33. أما تفجير البالون الذي يحقق أكبر عائد الآن فيحقق 42 على [2, 9, 2]، حيث إن تفجير بالون قيمته 2 أولًا يحقق 18 + 18 + 9 = 45. كل تفجير يغيّر أسعار البالونات التي تُفجَّر لاحقًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxCoins(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [2, 4, 3]
الإخراج المتوقع
33