House Robber
בתים עומדים בשורה לאורך רחוב, ו־nums[i] הוא סכום הכסף בבית i. אפשר לקחת כסף מכל הבתים שתבחרו, אך לעולם לא משני בתים שעומדים זה לצד זה. החזירו את הסכום הכולל הגדול ביותר שאפשר לקחת.
פונקציה
- numsinteger-array
- הכסף בכל בית, לפי סדר הרחוב
- מחזירהinteger
- הסכום הגדול ביותר שאפשר לקחת בלי לקחת משני בתים סמוכים
אילוצים
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- התשובה היא לכל היותר
5 × 106, ולכן היא נכנסת למספר שלם חתום בן 32 סיביות.
דוגמאות
- קלט
- nums = [5, 3, 4, 11, 2]
- פלט
- 16
- הסבר
- קחו 5 ו־11 מבתים 0 ו־3, וקבלו 16. מותר לדלג על שני בתים ברצף, וכאן האפשרות הזאת עדיפה על כל תוכנית אחרת: 5 + 4 + 2 = 11 ו־3 + 11 = 14.
- קלט
- nums = [3, 10, 3]
- פלט
- 10
- הסבר
- שני הבתים שבקצוות יחד נותנים 3 + 3 = 6. הבית האמצעי לבדו נותן 10, ולקיחתו פוסלת את שני הבתים השכנים לו.
- קלט
- nums = [2, 9, 3, 1, 8]
- פלט
- 17
- הסבר
- 9 ו-8 נמצאים בבתים 1 ו-4, שאינם שכנים, והתוצאה היא 17. בחירה של בית כן ובית לא החל מההתחלה נותנת רק 2 + 3 + 8 = 13.
+16 בדיקות נסתרות בשליחה
שאלת המשך
החזר את הבתים שיש לקחת וגם את הסכום הכולל. מה צריך לשמור מהטבלה כדי לבנות מחדש את הרשימה הזאת, והאם שני הסכומים המצטברים עדיין מספיקים לכך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
הסתכלו על הבית האחרון. תוכנית או לוקחת אותו או מדלגת עליו. מה כל בחירה משאירה לכם לפתור?
אם תדלג על בית
k-1, התוצאה הטובה ביותר היא התוצאה הטובה ביותר מביןk-1הבתים הראשונים. אם תיקח אותו, תוסיף אתnums[k-1]לתוצאה הטובה ביותר מביןk-2הבתים הראשונים. התשובה עבורkבתים היא הגדולה מבין השתיים.מלאו את הסכומים הטובים ביותר האלה מתחילת הרחוב, החל מ־0 כשאין בתים. כל אחד מהם זקוק רק לשניים הקודמים, לכן שני משתנים מספיקים.
פתרון
קיצורי הדרך המתבקשים נכשלים. בחירה בכל בית שני מפספסת תוכניות שמדלגות על שני בתים ברציפות, כמו 5 ו-11 ב-[5, 3, 4, 11, 2], ובחירה תחילה בבית העשיר ביותר נכשלת ב-[3, 4, 3], שבה 4 חוסם שני בתים שערכם יחד 6. מה שעובד הוא להחליט על בית אחד בכל פעם: הסכום המיטבי עד לבית מסוים תלוי רק בסכומים המיטביים עד לשני הבתים שלפניו.
נסו את שתי האפשרויות בכל בית
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
התבוננו בבית האחרון, בית n-1. כל תוכנית או מדלגת עליו או לוקחת אותו. אם היא מדלגת עליו, המיטב שהיא יכולה לעשות הוא התוכנית הטובה ביותר עבור n-1 הבתים הראשונים. אם היא לוקחת אותו, אי אפשר לקחת את בית n-2, ולכן מוסיפים את nums[n-1] לתוכנית הטובה ביותר עבור n-2 הבתים הראשונים. התשובה היא הגדול מבין השניים.
נכתוב זאת כפונקציה most(k), הסכום המרבי שאפשר לקחת מ-k הבתים הראשונים: 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 מיליון קריאות, ובבדיקות יש עד 10^4 בתים. הקריאות גם נערמות לעומק של n רמות, מעבר למגבלת ברירת המחדל של Python, שהיא 1000.
אלגוריתם
- כתבו פונקציית עזר
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[k] הוא הסכום המרבי שאפשר לקחת מ־k הבתים הראשונים. נוסחת הנסיגה: best[k] = max(best[k-1], best[k-2] + nums[k-1]): לדלג על בית k-1, או לקחת אותו נוסף על המיטב שמסתיים לפני השכן שלו. מקרי בסיס: best[0] = 0 וגם best[1] = nums[0]. סדר: k מ־2 ועד n, כי כל איבר מסתמך על שני האיברים שלפניו.
עבור [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]שני סכומים מצטברים
האינטואיציה
כל רשומה בטבלה קוראת רק את שתי הרשומות שלפניה. ברגע ש־best[k] ידוע, לא קוראים שוב את best[k-2]. לכן נשמור שני מספרים במקום הטבלה: twoBack, הסכום המרבי מהבתים עד שני צעדים אחורה, ו־oneBack, הסכום המרבי עד הבית הקודם.
עבור בית שמכיל x, הסכום המרבי החדש הוא max(oneBack, twoBack + x). לאחר מכן מזיזים: twoBack מקבל את הערך הישן של oneBack, ו־oneBack מקבל את הסכום המרבי החדש. שניהם מתחילים ב־0, שמייצג את הרחוב הריק שלפני הבית הראשון, ולכן אין צורך במקרה מיוחד עבור הבית הראשון: הסכום המרבי שלו הוא max(0, 0 + nums[0]).
עבור [5, 3, 4, 11, 2], הזוג הוא (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), ו־oneBack מסתיים ב־16. זמן העבודה זהה, O(n), לזה של הטבלה, והזיכרון מצטמצם ל־O(1).
אלגוריתם
- הציבו 0 ב־
twoBackוב־oneBack. - עבור כל סכום
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
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מקיצור דרך שעובד עבור קלטים קטנים, או מעדכון שני הסכומים בסדר הלא נכון.
- סכימת הבתים הזוגיים והבתים האי-זוגיים ובחירת הסכום הגדול יותר מפספסת תוכניות שמדלגות על שני בתים רצופים. עבור
[10, 1, 1, 10]שני הסכומים הם 11, אבל הבתים 0 ו-3 נותנים 20. - בחירת הבית העשיר ביותר תחילה נכשלת עבור
[3, 4, 3]: היא בוחרת את 4 וחוסמת את שני ה-3, שסכומם יחד הוא 6. - דריסת
oneBackלפני העתקתו אלtwoBackגורמת לאובדן הערך שהבית הבא זקוק לו. חשבו תחילה מהו הערך החדש הטוב ביותר, ואז הזיזו את הערכים, או הקצו את שניהם בבת אחת, אם השפה מאפשרת זאת. - קריאת
nums[1]או הגדרתbest[1]ו-best[2]מראש נכשלות ברחוב עם בית אחד. התחלת שני הסכומים ב-0 מייתרת את המקרה המיוחד. - ב-Lua וב-R, המערכים מתחילים ב-1, לכן הכסף שבבית
k-1נמצא ב-nums[k].
שאלות נפוצות4
מהי נוסחת הנסיגה של בעיית שודד הבתים?
הסכום הכולל הטוב ביותר מתוך k הבתים הראשונים הוא max(best[k-1], best[k-2] + nums[k-1]). או שמדלגים על בית k-1 ומשאירים את התוצאה הטובה ביותר מהבתים שלפניו, או שלוקחים את בית k-1 ומוסיפים אותו לתוצאה הטובה ביותר שמסתיימת לפני הבית הסמוך אליו. מקרי הבסיס הם 0 כשאין בתים ו-nums[0] כשיש בית אחד.
מהי סיבוכיות הזמן והמרחב של House Robber?
פתרון התכנות הדינמי עובר על כל בית פעם אחת, ולכן זמן הריצה שלו הוא O(n). טבלה מלאה צורכת O(n) מקום, ושמירת שני הסכומים האחרונים בלבד מצמצמת זאת ל־O(1). רקורסיה פשוטה ללא שמירת התשובות מבצעת בערך 1.6^n קריאות, שזהו גידול מעריכי.
למה לקחת כל בית שני לא פותר את בעיית שודד הבתים?
לפעמים התוכנית הטובה ביותר מדלגת על שני בתים ברצף. ב־[10, 1, 1, 10] סכום הבתים במיקומים הזוגיים וסכום הבתים במיקומים האי־זוגיים הם 11, ואילו בחירת הבית הראשון והבית האחרון נותנת 20. תכנות דינמי משווה בין דילוג לבחירה בכל בית, ולכן הוא מוצא את התוכניות האלה.
איך פותרים את בעיית שוד הבתים כשהבתים מסודרים במעגל?
במעגל, הבית הראשון והבית האחרון הם שכנים, ולכן אפשר לבחור לכל היותר באחד מהם בתוכנית. יש להריץ את הפתרון לרחוב ישר פעמיים: פעם אחת בלי הבית האחרון ופעם אחת בלי הבית הראשון, ולהחזיר את התוצאה הגדולה יותר. רחוב עם בית אחד הוא המקרה החריג היחיד: התשובה היא אותו בית.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def rob(nums):
# כתבו את הקוד כאןמקרה 1
מקרה 2
מקרה 3
קלט
nums = [5, 3, 4, 11, 2]
צפוי
16