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
הסבר: פוצץ את 4 הראשונים כדי לקבל 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

למה Burst Balloons בוחר את הבלון האחרון במקום את הראשון?

אחרי הפיצוץ הראשון, הבלונים שמשני צדדיו הופכים לשכנים, ולכן החלק השמאלי והחלק הימני עדיין משפיעים זה על זה ואי אפשר לפתור אותם בנפרד. הבלון האחרון ברצף נשאר במקומו בזמן שהאחרים מתפוצצים, ולכן שני הצדדים לעולם לא נפגשים, וכשהוא מתפוצץ, השכנים שלו הם הגבולות הקבועים של הרצף. כך כל רצף הופך לתת־בעיה עצמאית, וזה מה שתכנות דינמי דורש.

מהי סיבוכיות הזמן של Burst Balloons?

בטבלת המרווחים יש בערך 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

בעיות דומות