Burst Balloons

+10

لديك صف من البالونات معطى على هيئة nums، حيث يمثّل nums[i] الرقم الموجود على البالون i. تفقعها جميعًا، واحدًا تلو الآخر، بأي ترتيب تختاره. يؤدي تفقيع بالون إلى كسب left × nums[i] × right من العملات، حيث إن left وright هما الرقمان الموجودان على جارَيْه الحاليَّيْن: أقرب بالون على كل جانب ما زال في الصف. يُحتسب الجار المفقود، متجاوزًا أيًّا من طرفَي الصف، على أنه 1. بعد تفقيع بالون، يصبح الجاران متجاورين. أعد أكبر عدد من العملات يمكنك جمعه.

الدالة

maxCoins(nums: integer-array) → integer

numsinteger-array: الأرقام على البالونات، من اليسار إلى اليمين
تُرجعinteger: أكبر عدد من العملات التي يمكنك جمعها عن طريق فرقعة كل بالون

القيود

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
الإجابة أقل من 3 × 10⁸، لذا فهي تتسع في عدد صحيح موقّع ذي 32 بتًا.

أمثلة

المدخلات: nums = [2, 4, 3]
المخرجات: 33
الشرح: فجّر الأعداد الأربعة الأولى لتحصل على 2 × 4 × 3 = 24 قطعة نقدية. أصبح العددان 2 و3 متجاورين الآن، لذا فإن تفجير العدد 2 يمنحك 1 × 2 × 3 = 6، والعدد 3، بعد أن أصبح وحيدًا، يمنحك 1 × 3 × 1 = 3. يصبح المجموع 33، ولا يوجد ترتيب آخر يحقق نتيجة أفضل: فتفجير العدد الصغير 2 أولًا يحدّ مكسبك عند 24.

+15 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك أيضًا إرجاع ترتيب واحد متفجر يربح أكبر عدد من العملات؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

كل انفجار يغيّر البالونات المتجاورة، لذا فإن اختيارًا الآن يغيّر تكلفة كل انفجار لاحق. تجربة جميع الترتيبات تعني وجود n! تسلسلًا. التفكير في البالون الأول الذي سينفجر لا يقسم الصف أيضًا، لأن جانبيه يصبحان متجاورين. أما التفكير في البالون الأخير الذي سينفجر ضمن مقطع فينجح: فهو يبقى في مكانه بينما تختفي بقية البالونات، لذا يصبح المقطع على يساره والمقطع على يمينه مستقلين. يحل جدول للفترات عبر تلك المقاطع المسألة ضمن O(n³).

جرّب كل ترتيب للتفجير

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

اختر أي بالون لتفقعه الآن، واجمع left × value × right مع جارَيه الحاليين، وأزِله من الصف، ثم حلّ الصف الأقصر بالطريقة نفسها. افعل ذلك لكل اختيار واحتفظ بأفضل مجموع. تؤدي الدالة العودية burstAll(row) هذا بالضبط. فهي تستكشف كل ترتيب ممكن، لذا تكون الإجابة صحيحة.

لكن هذه الطريقة غير عملية للأحجام الحقيقية. في الفقعة الأولى هناك n خيارات، وفي الثانية n-1، وهكذا: أي n! ترتيبًا. بالنسبة إلى 12 بالونًا، يبلغ العدد بالفعل 479,001,600 ترتيب، وأكبر اختبار يتضمن 120 بالونًا. ولا يكفي حفظ النتائج لكل مجموعة من البالونات التي ما زالت موجودة، لأن عدد هذه المجموعات هو 2^n.

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

الخوارزمية

اكتب burstAll(row)، التي تُعيد أكبر عدد من العملات من البالونات في row.
لكل موضع k، اقرأ الجارين، مستخدمًا 1 عند كل طرف.
اكسب left × row[k] × right، وأضف ناتج burstAll للصف من دون row[k].
أعِد أفضل مجموع لجميع قيم k، أو 0 إذا كان الصف فارغًا.
استدعِ 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]. هذان لا ينفجران أبدًا، ويمثلان الجارين المفقودين عند الطرفين. انظر الآن إلى فجوة بين موضعين left وright لا يزال كلاهما قائمًا، واسأل: أي بالون داخل الفجوة سينفجر أخيرًا؟

لنفترض أنه k. بينما تنفجر البالونات الأخرى في الفجوة، يظل k موجودًا، واقفًا بينها كالجدار. لكل بالون بين left وk جيران من ذلك الجزء فقط، مع left وk كحدّين ثابتين، وينطبق الأمر نفسه على الجزء بين k وright. لذا فالجزآن مسألتان مستقلتان من النوع نفسه. عندما ينفجر k أخيرًا، يكون كل ما بين الحدّين قد اختفى، فيكون جاراه بالضبط left وright، ويحصل على vals[left] × vals[k] × vals[right] قطعة نقدية. أما اختيار البالون الأول فلا يؤدي إلى هذا التقسيم، لأن جانبيه يصبحان متجاورين.

وهذا يعطينا علاقة递归. تُرجع solve(left, right) أكبر عدد من القطع النقدية التي يمكن الحصول عليها من البالونات الواقعة تمامًا بين left وright: 0 عندما تكون الفجوة فارغة، وإلا فأكبر قيمة لـ solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] لكل k في الفجوة. الإجابة هي solve(0, m-1)، أي الفجوة بين الحشوتين.

بمفردها، تعود العلاقة递归 إلى الفجوة نفسها مرارًا وتكرارًا، لذا خزّن كل نتيجة في جدول memo[left][right] وأعِدها عند الزيارة التالية. يوجد نحو n²/2 فجوة، وتجرّب كل واحدة منها ما يصل إلى n بالونًا، لذا يكون العمل O(n³). استخدم -1 للفجوة التي لم تُحل بعد، لأن 0 إجابة صحيحة. ولا يتجاوز عمق العلاقة递归 n+1 استدعاءً، لأن كل استدعاء يعمل على فجوة أضيق.

الخوارزمية

أنشئ 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][right] أكبر عدد من القطع النقدية التي يمكن الحصول عليها من البالونات الواقعة حصريًا بين left وright، وتكون 0 للفجوة التي لا تحتوي على شيء. ابدأ بعرض 2، ثم زد العرض، ولكل فجوة بذلك العرض، جرّب كل k داخلها باعتباره البالون الأخير. الفجوتان best[left][k] وbest[k][right] أضيق، لذا تكونان قد حُسبتا بالفعل.

خذ [2, 4, 3]. بعد إضافة القيمتين الحارستين، تصبح vals = [1, 2, 4, 3, 1] في المواضع من 0 إلى 4، وتكون الإجابة best[0][4]. املأ الفجوات بدءًا من الأضيق:

العرض 2، بالون واحد في الداخل: best[0][2] = 1 × 2 × 4 = 8، best[1][3] = 2 × 4 × 3 = 24، best[2][4] = 4 × 3 × 1 = 12.
best[0][3]، البالونان 2 و4: إذا كان 2 الأخير، فالناتج 0 + 24 + 1 × 2 × 3 = 30؛ وإذا كان 4 الأخير، فالناتج 8 + 0 + 1 × 4 × 3 = 20. إذن القيمة 30.
best[1][4]، البالونان 4 و3: إذا كان 4 الأخير، فالناتج 0 + 12 + 2 × 4 × 1 = 20؛ وإذا كان 3 الأخير، فالناتج 24 + 0 + 2 × 3 × 1 = 30. إذن القيمة 30.
best[0][4]، البالونات الثلاثة كلها: إذا كان 2 الأخير، فالناتج 0 + 30 + 1 × 2 × 1 = 32؛ وإذا كان 4 الأخير، فالناتج 8 + 12 + 1 × 4 × 1 = 24؛ وإذا كان 3 الأخير، فالناتج 30 + 0 + 1 × 3 × 1 = 33. إذن القيمة 33.

ارجع إلى الخيارات الفائزة، وستحصل على الترتيب: يكون 3 الأخير، وقبله يكون 2 الأخير في الجزء الواقع إلى يساره، ويأتي 4 أولًا. وهذا يساوي 24 + 6 + 3 = 33.

حجم العمل هو نفسه كما في التخزين المؤقت: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 خطوة لـ 300 بالون، وجدول يضم 302 × 302 عددًا. تتجنب الحلقات العادية ملايين استدعاءات الدوال، ما يجعل هذه النسخة أسرع عدة مرات من الاستدعاء الذاتي في لغة مثل Python أو R.

الخوارزمية

أنشئ vals من nums مع إضافة 1 إلى كل طرف، واجعل m يساوي طولها.
أنشئ جدولًا بحجم m × m باسم best، واملأه بالقيمة 0.
لكل عرض من 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]

أخطاء شائعة وحالات حدّية

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

تفشل الترتيبات الجشعة. فرقعة أصغر بالون أولًا تعطي 24 في [2, 4, 3] بدلًا من 33، وفرقعة البالون الذي يحقق أكبر مكسب في اللحظة الحالية تعطي 42 في [2, 9, 2]، بينما فرقعة بالون قيمته 2 أولًا تعطي 18 + 18 + 9 = 45.
التقسيم بناءً على أول بالون يُفرقع مع استخدام جيرانه الأصليين، nums[k-1] × nums[k] × nums[k+1] بالإضافة إلى الجانبين، يحسب جيرانًا ربما اختفوا بالفعل. في [2, 4, 3] يعطي الناتج 44، وهو أكبر مما يمكن أن يحققه أي ترتيب حقيقي.
احتساب الحدود على أنها جزء من الفجوة. يظل left وright قائمين عند إخلاء الفجوة؛ ولا تُفرقع إلا البالونات الواقعة بينهما تمامًا.
ملء الجدول صفًا تلو الآخر مع زيادة left. عندها لا تكون best[k][right] عندما يكون k > left قد حُسبت بعد، فتُقرأ قيمتها على أنها 0. املأ الجدول حسب العرض، أو أنقص قيمة left.
استخدام 0 علامةً على أن الفجوة لم تُحل في التخزين المؤقت. فالفجوة التي تحتوي على بالونات قيمتها صفر تستحق فعلًا 0، لذا ستبدو غير محلولة إلى الأبد، وسيُعاد حلها عند كل زيارة. استخدم -1.
نسيان قيمتي 1 الحشو، ما يترك البالونات الطرفية بلا جار يُضرب بها.
في Lua وR، تمتد المواضع المحشوة من 1 إلى m، لذا تكون الإجابة best[1][m].

أسئلة شائعة4

لماذا تختار مسألة «تفجير البالونات» البالون الأخير بدلًا من الأول؟

بعد الانفجار الأول، يصبح البالونان على جانبيه متجاورين، لذلك يظل الجزء الأيسر والجزء الأيمن يؤثر أحدهما في الآخر، ولا يمكن حلّهما بشكل منفصل. يبقى البالون الأخير في مقطع ما في مكانه بينما تنفجر البالونات الأخرى، لذلك لا يلتقي الجانبان أبدًا، وعندما ينفجر تكون حدّا المقطع الثابتان هما جاراه. وهذا يجعل كل مقطع مسألة فرعية مستقلة، وهو ما تحتاج إليه البرمجة الديناميكية.

ما هو التعقيد الزمني لمسألة تفجير البالونات؟

يحتوي جدول الفترات على نحو n²/2 فجوة، وتحاول كل فجوة ما يصل إلى n بالونات بوصفها الأخيرة، لذا يكون الزمن O(n³) والذاكرة O(n²). بالنسبة إلى 300 بالون، يعادل ذلك نحو 4.5 × 10^6 خطوة. تجربة كل الترتيبات تتطلب O(n · n!).

هل يمكن حل مسألة تفجير البالونات بترتيب جشع؟

لا. تفشل كل قاعدة بسيطة في صف صغير. يؤدي تفجير أصغر بالون أولًا إلى كسب 24 في [2, 4, 3]، حيث يمكن كسب 33. ويؤدي تفجير البالون الذي يحقق أكبر عائد في الوقت الحالي إلى كسب 42 في [2, 9, 2]، حيث إن تفجير بالون قيمته 2 أولًا يحقق 45. يغيّر تفجير بالون أسعار البالونات التي تليه، لذا تحتاج إلى البرمجة الديناميكية على الفجوات.

لماذا نضيف 1 عند طرفَي المصفوفة؟

يُحتسب الجار المفقود بقيمة 1، لذا فإن بالوني الحشو ذوي القيمة 1 اللذين لا ينفجران يمنحان كل بالون حقيقي جارَين دون الحاجة إلى حالات خاصة. كما أنهما يشكّلان حدود المسألة بأكملها: الإجابة هي الفجوة بين بالوني الحشو، best[0][m-1].

Python

def maxCoins(nums):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [2, 4, 3]

المتوقع

Burst Balloons

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كل ترتيب للتفجير

الاستدعاء الذاتي عند البالون الأخير، مع مذكرة

املأ جدول الفترات حسب العرض

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة