אתגר תכנותי: שודד הבתים 2

או איך שודד חכם אחד משתמש בתכנות דינמי להבטחת חירותו

במדריך זה, נתמודד עם הבעיה הקלאסית "שודד הבתים 2" (leetcode 213) ונלמד כיצד להשתמש בתכנות דינמי (DP) כדי למקסם את השלל מבלי להפעיל את מערכת האזעקה. אתגר זה דומה לאחר איתו כבר התמודדנו – "שודד הבתים". הקושי נובע מכך שהבתים מסודרים במעגל, כך שהבית הראשון והאחרון הם שכנים. מגבלה זו מחייבת פתרון שונה במקצת.

תיאור הבעיה

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

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

דוגמה 1:

Input: houses = [3, 4, 3]
Output: 4

הסבר: אינך יכול לשדוד את הבתים הראשון והשלישי (3+3=6) בגלל שהם הקיצוניים ולכן הם סמוכים (כי הבתים מסודרים במעגל) מה שמשאיר אותך עם האפשרות לשדוד רק את הבית השני.

דוגמה 2:

Input:houses = [2, 3, 4, 2]
Output: 6

נסביר: כי השלל משוד הבתים הראשון והשלישי הוא הגבוה ביותר 2+4=6.

פתרון מבוסס תכנות דינאמי (DP)

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

1. שלב המדלג על הבית הראשון - עובר על המערך מהבית השני ועד האחרון.
2. שלב המדלג על הבית האחרון - עובר על המערך מהבית הראשון ועד הבית הלפני אחרון.

הפתרון אותו תחזיר הפונקציה הינו התוצאה המקסימלית מבין שני השלבים.

הקוד הבא מממש את הרעיון:

def rob(houses):
    # The idea: Dynamic programming similar to House Robber (1)
    # but the last and first items can't be used together,
    # so we run two DP routines:
    # 1. Exclude the first house when doing DP.
    # 2. Exclude the last house when doing DP.
    # Then, find which gives the highest result.

    len_houses = len(houses)

    # Validate base cases
    if len_houses == 0:
        return 0
    if len_houses == 1:
        return houses[0]
    if len_houses == 2:
        return 0

    # Exclude the first house
    dp_0 = [0] * len_houses
    dp_0[1] = houses[1]
    dp_0[2] = max(dp_0[1], houses[2])
    for idx in range(3, len_houses):
        dp_0[idx] = max(houses[idx] + dp_0[idx-2], dp_0[idx-1])

    # Exclude the last house
    dp_1 = [0] * (len_houses - 1)
    dp_1[0] = houses[0]
    dp_1[1] = max(dp_1[0], houses[1])
    for idx in range(2, len_houses-1):
        dp_1[idx] = max(houses[idx] + dp_1[idx-2], dp_1[idx-1])
  
    # Return the best result from either case
    return max(dp_0[-1], dp_1[-1])

נסביר:

• טיפול במקרי הבסיס:

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

• שני מערכי תכנות דינאמי DP לטיפול בשני המקרים:

  • dp_0 למקרה בו מדלגים על הבית הראשון.
  • dp_1 למקרה בו מדלגים על הבית האחרון.

• לולאה הרצה על מערכי ה-DP: בכל פעם שהלולאה רצה הפונקציה בוחרת בין 2 החלופות.

• תוצאה סופית: התוצאה אותה מחזירה הפונקציה היא המקסימום בין הפריטים האחרונים של מערכי התכנות הדינאמי dp_0 ו-dp_1.

נבדוק:

houses = [2, 3, 2]
print(rob(houses))  # Expected output: 3

houses = [1, 2, 3, 1]
print(rob(houses))  # Expected output: 4 (rob houses with values 1 and 3)

houses = [1, 2, 3]
print(rob(houses))  # Expected output: 3

houses = [3, 2, 2, 3]
print(rob(houses))  # Expected output: 5

houses = [1, 2, 4, 2, 10]
print(rob(houses))  # Expected output: 14

הערכת ביצועים

• סיבוכיות זמן: היות והפונקציה עוברת על כל המערך פעמיים סיבוכיות הזמן הינה O(N)

• סיבוכיות מקום: שני מערכי DP באורך N פריטים דורשים מקום נוסף בזיכרון המוערך כ-O(N)

פתרון מבוסס תכנות דינאמי לביצועו נדרשת סיבוכיות מקום O(1) בלבד

ניתן לצמצם את סיבוכיות המקום מ-O(N) ל-O(1) על ידי שימוש בשני משתנים במקום בטבלת DP הדורשת מערך למימושה, כאשר:

• המשתנה הראשון מייצג את הערך עבור האינדקס הנוכחי פחות 1 (idx-1).
• המשתנה השני מייצג את הערך עבור האינדקס הנוכחי פחות 2 (idx-2).

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

אחת הדרכים לעשות זאת היא הבאה:

def rob(houses):
    # The idea: Similar DP as House Robber (1), but with O(1) space.
    # We run two cases:
    # 1. Exclude the first house.
    # 2. Exclude the last house.
    # And we maintain only two variables for each case.
    if not houses:
        return 0

    len_houses = len(houses)

    if len_houses == 1:
        return houses[0]
    if len_houses == 2:
        return 0

    # Exclude the first house
    # Here, we start with houses[1] and houses[2]
    prev = houses[1]
    cur = max(houses[2], prev)
    for idx in range(3, len_houses):
        cur, prev = max(prev+houses[idx], cur), cur
    max_first_item_excluded = cur

    # Exclude the last house
    prev = houses[0]
    cur = max(houses[1], prev)
    for idx in range(2, len_houses-1):
        cur, prev = max(prev + houses[idx], cur), cur
    max_last_item_excluded = cur

    # Return the best result from the two cases
    return max(max_first_item_excluded, max_last_item_excluded)

נסביר:

• הפחתת המקום הנדרש בזיכרון: במקום להשתמש במערך DP שלם, נשתמש ב-2 משתנים: `cur` לתוכו נציב את התוצאה הטובה ביותר עד לפריט הלפני אחרון. `prev` בשביל התוצאה הכי טובה עד לפריט השני לפני האחרון.

• נאתחל את המשתנים תוך התחשבות בשני המקרים:

  • כדי להשמיט את הבית הראשון, נאתחל את המשתנים:

    prev = houses[1]
    cur = houses[2]

  • כדי להשמיט את הבית האחרון, נאתחל את המשתנים:

    prev = houses[0]
    cur = houses[1]

• עדכון דינאמי של המשתנים: עדכון המשתנים נעשה בתוך לולאה באופן הבא:

  cur, prev = max(prev+houses[idx], cur), cur

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

• התוצאה הסופית: היא ערך המקסימום בין שני המקרים.

יישום עקרון DRY לצורך ייעול הקוד

"Don't repeat yourself"
(the DRY principle in coding)

טוב יותר ממורכבות מקום O(1) זה להשיג את התוצאה בלי לחזור על הקוד. לצורך כך, נמצה את הטיפול בלולאה לפונקצית עזר `rob_in_between()`.

כך נעשה זאת:

def rob(houses):
    if not houses:
        return 0
    len_houses = len(houses)
    if len_houses == 1:
        return houses[0]
    if len_houses == 2:
        return 0

    def rob_between(start, end):
        prev = houses[start]
        cur = max(prev, houses[start+1])
        for i in range(start+2, end):
            prev, cur = cur, max(prev+houses[i], cur)
        return cur

    skip_first = rob_between(1, len_houses)
    skip_last = rob_between(0, len_houses-1)

    return max(skip_first, skip_last)

נסביר:

פונקצית העזר `rob_between()` מקבלת את האינדקסים עליהם היא צריכה לרוץ בלולאה. הפונקציה מאתחלת את המשתנים `prev` ו-`cur`, ובתוך לולאה היא רצה בין האינדקסים שהיא קיבלה כפרמטרים. כך היא צוברת את ערכי המקסימום כשאת ערך המקסימום מהאיטרציה האחרונה הפונקציה מחזירה כפלט.

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

נסכם

בעיית "שודד הבתים II" ממחישה כיצד ניתן להתאים תכנות דינמי למגבלות מורכבות יותר – במקרה הזה, סידור מעגלי של בתים. התחלנו עם פתרון פשוט המשתמש במערכי DP עם סיבוכיות מקום O(N), לאחר מכן שיפרנו את הפתרון לסיבוכיות מקום O(1) על ידי שימוש בשני משתנים בלבד, ולבסוף יישמנו את עקרון ה-DRY (אל תחזור על עצמך) על ידי מיצוי הלוגיקה המשותפת לפונקציית עזר. טכניקות אילו לא רק מייעלות את הפתרון במונחי ניצול זיכרון, אלא גם משפרות את קריאות הקוד ותחזוקתו.

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

מאחל שינעם לך קידודך, ושתמיד תצליח למקסם את הרווחים מבלי שיקראו לשוטרים!

מדריכים נוספים שעשויים לעניין אותך

אתגר תכנותי: שודד הבתים

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

אתגר תכנותי Decode ways - פענוח הדרכים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים