Unique Paths

Q: מהי הנוסחה למספר המסלולים הייחודיים?

התשובה היא המקדם הבינומי C(m+n-2, m-1) . בכל מסלול מבצעים m-1 צעדים למטה ו- n-1 צעדים ימינה בסדר כלשהו, ובחירה של אילו מתוך m+n-2 הצעדים יהיו למטה קובעת את המסלול. עבור רשת בגודל 3 × 4, ‏C(5, 2) = 10.

בינוניתכנון דינמי מתמטיקה וסימולציה

+10

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

פונקציה

uniquePaths(m: integer, n: integer) → integer

minteger: מספר השורות ברשת
ninteger: מספר העמודות ברשת
מחזירהinteger: מספר המסלולים השונים מהתא השמאלי העליון לתא הימני התחתון

אילוצים

1 ≤ m, n ≤ 100
התשובה היא לכל היותר 2 × 10⁹, ולכן היא נכנסת למספר שלם מסומן בן 32 סיביות.

דוגמאות

קלט: m = 3n = 4
פלט: 10
הסבר: בכל מסלול יש 2 צעדים למטה ו-3 צעדים ימינה, ובסך הכול 5 צעדים. המסלול נקבע לפי 2 מתוך 5 הצעדים שנעים למטה, ויש 10 דרכים לבחור אותם.

+14 בדיקות נסתרות בשליחה

שאלת המשך

עבור רשת בגודל 100 × 100, התשובה מכילה 59 ספרות. איך היית מחזיר אותה מודולו 10^9+7 באמצעות הנוסחה, כאשר חלוקה ב־i כבר לא עובדת?

רמזים

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

נפתחו 0 מתוך 3

פתרון

אין טעם למנות את המסלולים אחד־אחד: ברשת בגודל 17 × 17 יש כבר 601,080,390 מסלולים. צריך לספור בלי למנות אותם. המסלולים לתא הם המסלולים לתא שמעליו ועוד המסלולים לתא שמשמאלו, וכך הרשת הופכת לטבלה שממלאים במעבר אחד. מסלול הוא גם פשוט סדרה של צעדים למטה וימינה, וזה מוביל לנוסחה סגורה.

ספרו כל מסלול באמצעות רקורסיה

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

האינטואיציה

חשוב על המהלך האחרון של הרובוט אל התא הימני-תחתון. הוא הגיע מלמטה מהתא שמעליו או מימין מהתא שמשמאלו, אף פעם לא משניהם. לכן המסלולים דרך רשת בגודל m × n הם המסלולים דרך הרשת עם שורה אחת פחות, uniquePaths(m-1, n), ועוד המסלולים דרך הרשת עם עמודה אחת פחות, uniquePaths(m, n-1).

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

זה איטי, כי כל מסלול מסתיים במקרה בסיס שמחזיר 1, ולכן מספר הקריאות הוא לפחות כמספר המסלולים. רשת בגודל 17 × 17 דורשת יותר מ-600 מיליון קריאות, והבדיקות מגיעות עד לתשובות של כמעט 1.6 × 10^9. מחשבים את אותן רשתות קטנות יותר פעמים רבות: מגיעים ל-(m-1, n-1) פעם אחת מכל אחד משני המצבים הקודמים שלו, והקריאות החוזרות מתרבות ככל שמתקדמים מטה.

אלגוריתם

אם m או n הם 1, החזירו 1: המסלול היחיד הוא קו ישר.
אחרת, ספרו את המסלולים שהצעד האחרון בהם הוא למטה, uniquePaths(m-1, n).
ספרו את המסלולים שהצעד האחרון בהם הוא ימינה, uniquePaths(m, n-1).
החזירו את הסכום שלהם.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

מלאו את הרשת שורה אחת בכל פעם

האינטואיציה

הרקורסיה שואלת שוב ושוב על אותם תאים, ויש רק m × n תאים. ספרו את המסלולים לכל תא פעם אחת, בסדר שבו התאים שאתם צריכים כבר מוכנים.

מצב: paths[r][c] הוא מספר המסלולים מהתא השמאלי העליון לשורה r, עמודה c. נוסחת נסיגה: paths[r][c] = paths[r-1][c] + paths[r][c-1], המסלולים שמגיעים מלמעלה ועוד המסלולים שמגיעים משמאל. מקרי בסיס: לכל תא בשורה העליונה ובעמודה השמאלית יש מסלול אחד, קו ישר. סדר: שורה אחר שורה, משמאל לימין, כך שהתא שמעל והתא שמשמאל כבר מולאו לפני שצריך אותם.

עבור m = 3 ו-n = 4 השורות הן 1 1 1 1, אחר כך 1 2 3 4, ואז 1 3 6 10, והתשובה היא התא האחרון, 10.

עכשיו שימו לב למה שהמילוי קורא: רק את השורה שמעל ואת השורה שאתם ממלאים. לכן שמרו שורה אחת. לפני שאתם מעדכנים את row[c] הוא עדיין מכיל את הספירה מהשורה שמעל, ו-row[c-1] כבר מכיל את הספירה החדשה שמשמאלו, ולכן row[c] += row[c-1] היא כל נוסחת הנסיגה. זמן הריצה נשאר O(m × n), והזיכרון מצטמצם מ-O(m × n) ל-O(n).

אלגוריתם

צרו את row עם n איברים, שכולם 1: השורה העליונה.
חזרו על הפעולה m-1 פעמים, פעם אחת עבור כל שורה שמתחת לשורה העליונה.
בכל שורה, עבור c מ-1 עד n-1, הוסיפו את row[c-1] אל row[c]. הערך של row[0] נשאר 1: זו העמודה השמאלית.
החזירו את row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

סופרים את המהלכים באמצעות מקדם בינומי

האינטואיציה

כל מסלול כולל בדיוק m-1 צעדים למטה ו־n-1 צעדים ימינה, ובסך הכול m+n-2 צעדים, בסדר כלשהו. כל סדר הוא מסלול תקין: הרובוט אף פעם לא מבצע יותר מ־m-1 צעדים למטה או n-1 צעדים ימינה, ולכן הוא אף פעם לא יוצא מהלוח. לכן מסלול הוא למעשה בחירה של m-1 צעדים מתוך m+n-2 הצעדים שיופנו למטה, והתשובה היא המקדם הבינומי C(m+n-2, m-1).

הטבלה מהגישה הקודמת היא משולש פסקל שהוטה על צדו, ולכן שתי הגישות מניבות את אותה תוצאה. כדי לחשב את המקדם בלי עצרות ענקיות, בונים אותו גורם אחר גורם. עם N = m+n-2 ו־k = min(m, n)-1, מכפילים ב־N-k+i ואז מחלקים ב־i, עבור i מ־1 עד k. אחרי שלב i, הערך המצטבר הוא C(N-k+i, i), מספר שלם, ולכן כל חילוק מדויק.

עבור m = 3 ו־n = 4: N = 5, k = 2, והערך מתקדם כך: 1 × 4 / 1 = 4, ואז 4 × 5 / 2 = 10. בחירה לאורך הצלע הקצרה יותר משאירה את הלולאה עם 99 צעדים לכל היותר. המכפלה לפני החילוק האחרון היא k כפול התשובה. עבור לוח בגודל 17 × 17, זהו 16 × 601,080,390, כלומר בערך 9.6 × 10^9, מעבר לטווח של 32 סיביות, ולכן יש לשמור את הערך במספר שלם של 64 סיביות.

אלגוריתם

הגדירו N = m+n-2, מספר הצעדים, ואת k = min(m, n)-1.
התחילו ספירה של 64 סיביות בערך 1.
עבור i מ-1 עד k, הכפילו את הספירה ב-N-k+i, ואז חלקו אותה ב-i.
החזירו את הספירה.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

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

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

חישוב (m+n-2)! וחלוקה בשתי העצרת האחרות גורמים לגלישה הרבה לפני שהתשובה עצמה חורגת מהטווח: 21! כבר חורג מטווח 64 הביטים, ו-m+n-2 מגיע ל-105 ברשת של 100 × 7.
חלוקה לפני הכפל, כמו ב-count / i * (N-k+i), גורמת לחיתוך, כי count לא תמיד מתחלק ב-i. הכפילו קודם: המכפלה תמיד מתחלקת בדיוק.
המכפלה count × (N-k+i) יכולה לחרוג מ-2^31 גם כשהתשובה אינה חורגת ממנו. שמרו אותה במספר שלם של 64 ביטים.
השארת השורה העליונה או העמודה השמאלית בערך 0 במקום 1 הופכת את כל התאים ל-0. ברשת עם שורה אחת או עמודה אחת יש בדיוק מסלול אחד.
החלפת השורות והעמודות אינה משנה את התשובה, מכיוון ש-C(m+n-2, m-1) = C(m+n-2, n-1).

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

מהי הנוסחה למספר המסלולים הייחודיים?

התשובה היא המקדם הבינומי C(m+n-2, m-1). בכל מסלול מבצעים m-1 צעדים למטה ו-n-1 צעדים ימינה בסדר כלשהו, ובחירה של אילו מתוך m+n-2 הצעדים יהיו למטה קובעת את המסלול. עבור רשת בגודל 3 × 4, ‏C(5, 2) = 10.

מהי סיבוכיות הזמן של Unique Paths?

טבלת התכנות הדינמי דורשת זמן O(m × n) ומקום O(n) כששומרים שורה אחת. נוסחת הבינום דורשת זמן O(min(m, n)) ומקום O(1). רקורסיה פשוטה מבצעת לפחות מספר קריאות כמספר המסלולים, שהוא אקספוננציאלי ביחס ל-m + n.

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

השתמשו באותה טבלה, והגדירו את מספר המסלולים בתא חסום ל־0, כדי שאף מסלול לא יעבור דרכו. השורה העליונה והעמודה השמאלית כבר אינן כולן 1: לכל תא אחרי תא חסום בשורה העליונה יש 0 מסלולים. הנוסחה כבר לא עובדת, כי היא מניחה שכל סדר של תנועות מותר.

למה טבלת המסלולים הייחודיים תואמת למשולש פסקל?

כל תא מחבר את התא שמעליו ואת התא שמשמאלו, וזהו הכלל שבונה את משולש פסקל, כשקוראים אותו לאורך האלכסונים שלו. התא בשורה r ובעמודה c מכיל C(r+c, r), ולכן התא בפינה הימנית התחתונה מכיל C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

m = 3
n = 4

צפוי

Unique Paths

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

ספרו כל מסלול באמצעות רקורסיה

מלאו את הרשת שורה אחת בכל פעם

סופרים את המהלכים באמצעות מקדם בינומי

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

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

בעיות דומות