Burst Balloons

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

זמן O(n³) וזיכרון O(n²) : בערך n²/2 פערים, כשבכל אחד מהם מנסים עד n בלונים בתור האחרון. עבור 300 בלונים מדובר בכ־4.5 × 10^6 צעדים. ניסיון של כל הסדרים הוא O(n · n!) .

Q: האם אפשר לפתור את Burst Balloons באמצעות סדר חמדני?

לא. פיצוץ הבלון הקטן ביותר קודם מניב 24 עבור [2, 4, 3] , אף שאפשר להגיע ל־33. פיצוץ הבלון שמשתלם ביותר כרגע מניב 42 עבור [2, 9, 2] , אף שפיצוץ של 2 קודם מניב 18 + 18 + 9 = 45. כל פיצוץ משנה את המחירים של הפיצוצים הבאים.

קשהתכנון דינמי

+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, מקבל 1 × 2 × 3 = 6, וה־3 מקבל 3: בסך הכול 33.

שאלת המשך

האם תוכל גם להחזיר סדר מתפוצץ אחד שמרוויח הכי הרבה מטבעות?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

כל פיצוץ משנה מי נמצא ליד מי, ולכן הבלון הראשון שתפוצץ לא מפריד את השורה: שני צידיו הופכים לשכנים. הבלון האחרון שמתפוצץ ברצף כן עושה זאת. הוא נשאר בזמן שכל השאר נעלמים, ולכן הרצפים משני צדדיו בלתי תלויים, וטבלת מרווחים על פני רצפים פותרת את הבעיה ב־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]. ה־1 בקצוות לעולם לא מתפוצצים ומחליפים את השכנים החסרים. נגדיר את solve(left, right) כמספר המטבעות המרבי שאפשר לקבל מהבלונים שנמצאים בדיוק בין שני המיקומים שנותרו.

נניח שהבלון k הוא האחרון שמתפוצץ במרווח הזה. כל בלון אחר במרווח מתפוצץ בזמן ש־k משמש כחומה, ולכן בחלק שבין left ל־k יש רק את הבלונים שלו ושני גבולות קבועים, וכך גם בחלק שבין k ל־right. כש־k מתפוצץ, השכנים שלו הם בדיוק left ו־right. לכן התוצאה הטובה ביותר עבור המרווח היא, עבור כל k, התוצאה הטובה ביותר של שני החלקים בתוספת vals[left] × vals[k] × vals[right]. התשובה היא המרווח שבין שני ה־1 בקצוות. יש בערך 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

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

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

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

זמן O(n³) וזיכרון O(n²): בערך n²/2 פערים, כשבכל אחד מהם מנסים עד n בלונים בתור האחרון. עבור 300 בלונים מדובר בכ־4.5 × 10^6 צעדים. ניסיון של כל הסדרים הוא O(n · n!).

האם אפשר לפתור את Burst Balloons באמצעות סדר חמדני?

לא. פיצוץ הבלון הקטן ביותר קודם מניב 24 עבור [2, 4, 3], אף שאפשר להגיע ל־33. פיצוץ הבלון שמשתלם ביותר כרגע מניב 42 עבור [2, 9, 2], אף שפיצוץ של 2 קודם מניב 18 + 18 + 9 = 45. כל פיצוץ משנה את המחירים של הפיצוצים הבאים.

def maxCoins(nums):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [2, 4, 3]

הפלט הצפוי

Burst Balloons

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסה כל סדר התפרצות

רקורסיה על הבלון האחרון, עם תזכורת

מלאו את טבלת המרווחים לפי רוחב

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות