House Robber

Q: למה בחירת כל בית שני לא פותרת את בעיית שודד הבתים?

לפעמים התוכנית הטובה ביותר מדלגת על שני בתים ברצף. ב־ [10, 1, 1, 10] סכום הבתים הזוגיים וסכום הבתים האי־זוגיים הם 11, ואילו הבית הראשון והאחרון נותנים 20.

בינוניתכנון דינמי

+10

בתים עומדים בשורה לאורך רחוב, ו־nums[i] הוא סכום הכסף בבית i. מותר לך לקחת כסף מכל הבתים שתבחר, אך לעולם לא משני בתים שעומדים זה לצד זה. החזר את הסכום הכולל הגדול ביותר שתוכל לקחת.

פונקציה

rob(nums: integer-array) → integer

numsinteger-array: הכסף בכל בית, לפי סדר הבתים ברחוב
מחזירהinteger: הסכום הכולל הגדול ביותר שאפשר לקחת מבלי לקחת משני בתים סמוכים

אילוצים

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
התשובה היא לכל היותר 5 × 10⁶, ולכן היא מתאימה למספר שלם חתום בן 32 סיביות.

דוגמאות

קלט: nums = [5, 3, 4, 11, 2]
פלט: 16
הסבר: קחו 5 ו-11 מהבתים 0 ו-3, כדי לקבל 16. מותר לדלג על שני בתים ברצף, וכאן זה עדיף על כל תוכנית אחרת: 5 + 4 + 2 = 11 ו-3 + 11 = 14.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

קיצורי דרך נכשלים: בחירה בכל בית שני מפספסת את 5 ואת 11 ב־[5, 3, 4, 11, 2], ובחירה קודם בבית העשיר ביותר מובילה להפסד ב־[3, 4, 3]. החליטו לגבי בית אחד בכל פעם: הסכום הטוב ביותר עד בית מסוים תלוי רק בסכומים הטובים ביותר עד שני הבתים שלפניו.

נסו את שתי האפשרויות בכל בית

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

כל תוכנית או מדלגת על הבית האחרון או לוקחת אותו. דילוג משאיר את התוכנית הטובה ביותר עבור n-1 הבתים הראשונים; לקיחה מוסיפה את nums[n-1] לתוכנית הטובה ביותר עבור n-2 הבתים הראשונים. לכן most(k) = max(most(k-1), most(k-2) + nums[k-1]), כאשר most(0) = 0 ו-most(1) = nums[0]. שני הענפים מכסים כל תוכנית אפשרית, ולכן התשובה נכונה.

הענפים חופפים: most(k-1) מבקשת שוב את most(k-2), ומספר הקריאות גדל כמו מספרי פיבונאצ'י, בערך 1.6^n. ארבעים בתים דורשים יותר מ-300 מיליון קריאות, ו-n מגיע ל-10^4.

אלגוריתם

כתבו פונקציית עזר most(k) שמחזירה את הסכום המרבי שאפשר לקחת מהבתים הראשונים k.
החזירו 0 כאשר k הוא 0, ואת nums[0] כאשר k הוא 1.
אחרת, חשבו את skip = most(k-1) ואת take = most(k-2) + nums[k-1].
החזירו את הגדול מבין השניים. התשובה היא most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

טבלה מלמטה למעלה

האינטואיציה

הרקורסיה שואלת רק על most(0) עד most(n): n + 1 שאלות. ענו על כל אחת פעם אחת בטבלה best, החל מ-best[0] = 0 ו-best[1] = nums[0], ומלאו כלפי מעלה החל מ-k = 2, כך ששתי הרשומות שכל קריאה קוראת כבר נמצאות שם.

עבור [5, 3, 4, 11, 2] הטבלה היא 0, 5, 5, 9, 16, 16. ב-k = 4, דילוג על בית 3 משאיר את best[3] = 9, ואילו הוספת 11 שלו ל-best[2] = 5 נותנת 16, וזה עדיף. כל רשומה דורשת השוואה אחת: זמן O(n) ומקום O(n).

אלגוריתם

צרו טבלה בשם best עם n + 1 איברים.
הגדירו best[0] = 0 ואת best[1] = nums[0].
עבור k מ־2 עד n, הגדירו את best[k] כגדול מבין best[k-1] ו־best[k-2] + nums[k-1].
החזירו את best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

שני סכומים מצטברים

האינטואיציה

כל איבר קורא רק את שני האיברים שלפניו, לכן שומרים שני מספרים במקום את הטבלה: twoBack ו-oneBack, הסכומים המרביים עד שני בתים אחורה ועד הבית הקודם. עבור בית שמכיל x, הסכום המרבי החדש הוא max(oneBack, twoBack + x); ואז מזיזים את שניהם קדימה. שניהם מתחילים ב-0, הרחוב הריק שלפני הבית הראשון, כך שלרחוב שיש בו בית אחד אין צורך במקרה מיוחד. זמן הריצה נשאר O(n), והזיכרון מצטמצם ל-O(1).

אלגוריתם

הגדר את twoBack ואת oneBack ל־0.
עבור כל סכום x ב־nums, חשב את current = max(oneBack, twoBack + x).
העבר את oneBack אל twoBack, ואז את current אל oneBack.
אחרי הבית האחרון, החזר את oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

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

דריסה של oneBack לפני העתקתו לתוך twoBack. הבית הבא קורא אז את הסכום הכולל הלא נכון. חשבו קודם את התוצאה הטובה ביותר החדשה ואז בצעו הזחה, או הקצו את שניהם בבת אחת.
קריאה של nums[1], או הגדרה מראש של best[1] ושל best[2]. שניהם נכשלים ברחוב שיש בו בית אחד, כגון [0].
ב-Lua וב-R, מערכים מתחילים ב-1, ולכן הכסף בבית k-1 הוא nums[k].

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

מהי סיבוכיות הזמן והמקום של שודד הבתים?

תכנות דינמי בוחן כל בית פעם אחת, ולכן נדרש זמן O(n). טבלה מלאה צורכת מקום O(n), ושמירה של שני הסכומים האחרונים בלבד מצמצמת זאת ל־O(1). רקורסיה פשוטה ללא שמירת התשובות מבצעת בערך 1.6^n קריאות.

למה בחירת כל בית שני לא פותרת את בעיית שודד הבתים?

לפעמים התוכנית הטובה ביותר מדלגת על שני בתים ברצף. ב־[10, 1, 1, 10] סכום הבתים הזוגיים וסכום הבתים האי־זוגיים הם 11, ואילו הבית הראשון והאחרון נותנים 20.

איך פותרים את בעיית שודד הבתים כשהבתים מסודרים במעגל?

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [5, 3, 4, 11, 2]

הפלט הצפוי

House Robber

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו את שתי האפשרויות בכל בית

טבלה מלמטה למעלה

שני סכומים מצטברים

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

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

בעיות דומות