Climbing Stairs

Q: למה טיפוס במדרגות הוא בעיית פיבונאצ'י?

כל טיפוס אל מדרגה n מסתיים בצעד אחד מ־ n-1 או בצעד של שניים מ־ n-2 , ולכן ways(n) = ways(n-1) + ways(n-2) . זהו כלל פיבונאצ'י. עם ways(1) = 1 ו־ ways(2) = 2 , הספירות הן 1, 2, 3, 5, 8, 13, וזוהי סדרת פיבונאצ'י המוזזת מקום אחד: ways(n) = F(n+1) .

Q: מהי סיבוכיות הזמן של טיפוס במדרגות?

הלולאה מלמטה למעלה מבצעת n-2 פעולות חיבור, ולכן זמן הריצה שלה הוא O(n) והיא משתמשת במקום נוסף של O(1) . הרקורסיה הרגילה היא אקספוננציאלית: מספר הקריאות שלה גדל פי כ־1.618 בכל צעד ומגיע ל־2269806339, כלומר בערך 2.3 × 10^9 , כאשר n = 45 . שימוש בזיכרון מטמון מוריד את זמן הריצה של הרקורסיה ל־ O(n) ואת המקום שהיא צורכת ל־ O(n) .

קלתכנון דינמי רקורסיה

+10

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

פונקציה

climbStairs(n: integer) → integer

ninteger: מספר המדרגות בגרם המדרגות
מחזירהinteger: מספר הרצפים השונים של צעדים בני 1 ו-2 שמגיעים לצעד n

אילוצים

1 ≤ n ≤ 45
התשובה נכנסת לטווח של מספר שלם חתום בן 32 סיביות: n = 45 נותן 1836311903.

דוגמאות

קלט: n = 3
פלט: 3
הסבר: אפשר לטפס בשלושה צעדים כ־1, 1, 1, כ־1, 2 או כ־2, 1, ולכן יש 3 דרכים.

קלט: n = 5
פלט: 8
הסבר: כל טיפוס לשלב 5 מסתיים בצעד אחד משלב 4 (5 דרכים להגיע אליו) או בשני צעדים משלב 3 (3 דרכים), לכן התשובה היא 5 + 3 = 8.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

אי אפשר לרשום כל טיפוס: בגרם מדרגות בן 45 שלבים יש 1836311903 אפשרויות. הדרך לפתרון היא המהלך האחרון. כל טיפוס לשלב n עובר בשלב n-1 או בשלב n-2 ממש לפני הסוף, ולכן מתקיים ways(n) = ways(n-1) + ways(n-2), נוסחת הנסיגה של פיבונאצ'י. חשבו זאת מלמטה למעלה, וכל מה שצריך הוא שני משתנים.

רקורסיה פשוטה במהלך האחרון

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

האינטואיציה

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

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

התשובה נכונה, אבל העבודה מתנפחת במהירות. climbStairs(5) מבקשת את מדרגה 3 פעמיים ואת מדרגה 2 שלוש פעמים, 9 קריאות בסך הכול, ומספר הקריאות גדל בדומה לתשובות עצמן. עבור n = 45 הפונקציה מבצעת 2269806339 קריאות, בערך 2.3 × 10^9, הרבה יותר מדי עבור מגבלת זמן. עומק הרקורסיה הוא רק n רמות, ולכן המחסנית משתמשת ב-O(n) מקום.

אלגוריתם

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

def climbStairs(n):
    if n <= 2:
        return n  # 1 step: one way, 2 steps: two ways
    return climbStairs(n - 1) + climbStairs(n - 2)

רקורסיה עם זיכרון מטמון

האינטואיציה

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

כעת כל אחת מהספירות משלב 3 עד שלב n מחושבת פעם אחת, עם חיבור אחד. עבור n = 5, הקריאות יורדות עד שלב 2 פעם אחת, ואז התשובות חוזרות כלפי מעלה כ־3, 5 ו־8, והבקשה השנייה עבור שלב 3 היא חיפוש במטמון. זהו זמן ריצה של O(n) במקום מיליארדי קריאות.

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

אלגוריתם

צור מערך זיכרון עם n + 1 תאים, שכולם מכילים 0.
בעזר הרקורסיבי, החזר את k כאשר k ≤ 2.
אם תא הזיכרון עבור k מכיל 0, מלא אותו בסכום התוצאות של העזר עבור k-1 ו-k-2.
החזר את תא הזיכרון.
קרא לעזר עם n.

def climbStairs(n):
    memo = [0] * (n + 1)  # memo[k] = ways to reach step k, 0 = not known yet

    def ways(k):
        if k <= 2:
            return k
        if memo[k] == 0:
            memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)

מלמטה למעלה עם שני משתנים

האינטואיציה

הפכו את כיוון הרקורסיה. במקום להתחיל מלמעלה ולשאול כלפי מטה, התחילו מלמטה ובנו כלפי מעלה. כשמחשבים את מספר האפשרויות עבור שלב k, מספרי האפשרויות עבור k-1 ו־k-2 כבר ידועים, ואף פעם לא קוראים שוב ערכים ישנים יותר. לכן שני משתנים מחליפים את כל טבלת הזיכרון.

השתמשו ב־prev כדי לשמור את מספר האפשרויות עבור שלב k-2, וב־curr כדי לשמור את מספר האפשרויות עבור שלב k-1. התחילו עם prev = 1 ו־curr = 2, מספרי האפשרויות עבור שלבים 1 ו־2. בכל שלב חברו אותם לתוך next, ואז קַדמו את הצמד. עבור n = 5 הצמד מתקדם מ־(1, 2) ל־(2, 3), (3, 5) ו־(5, 8), ו־curr = 8 היא התשובה.

הלולאה רצה n-2 פעמים, עם פעולת חיבור אחת בכל פעם: זמן O(n), והיא שומרת שלושה מספרים שלמים: מקום O(1). חשבו את next לפני שאתם דורכים על הערך של prev, אחרת הסכום ישתמש בערך שגוי.

אלגוריתם

אם n ≤ 2, החזר את n.
הגדר prev = 1 ואת curr = 2.
עבור k מ-3 עד n, חשב את next = prev + curr, ואז הגדר את prev = curr ואת curr = next.
החזר את curr.

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2  # ways to reach steps 1 and 2
    for _ in range(n - 2):
        prev, curr = curr, prev + curr
    return curr

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

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

הגשת רקורסיה פשוטה. היא עוברת את הבדיקות הקטנות, אבל אז נדרשות בערך 2.3 × 10^9 קריאות עבור n = 45. שמור כל ספירה פעם אחת.
מקרי בסיס שגויים. בשני צעדים יש שתי דרכים לעלות: 1, 1 ו-2. החזרת 1 עבור n = 2 מזיזה את כל התשובות הבאות: עבור n = 3 תקבל 2 במקום 3.
ספירת אפשרויות במקום רצפים. 1, 2 ו-2, 1 הן שתי דרכים לעלות. ספירת מספר צעדי ה-2 בלבד נותנת n/2 + 1, כלומר 3 עבור n = 5 במקום 8.
מילוי טבלה בלי בדיקת הגנה. כאשר n = 1, בטבלה בת n + 1 = 2 תאים אין מקום לספירת דרכים לעלות 2 צעדים. החזר מיד את n כאשר n ≤ 2.
חישוב צעד אחד רחוק מדי. מספר הדרכים לעלות 45 צעדים, 1836311903, נכנס ב-32 ביטים, אבל מספר הדרכים לעלות 46 צעדים הוא 2971215073, והוא לא נכנס. לולאה שמחשבת ערך אחד נוסף גורמת לגלישה למספר שלילי ב-Java, ב-C או ב-C#.

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

למה טיפוס במדרגות הוא בעיית פיבונאצ'י?

כל טיפוס אל מדרגה n מסתיים בצעד אחד מ־n-1 או בצעד של שניים מ־n-2, ולכן ways(n) = ways(n-1) + ways(n-2). זהו כלל פיבונאצ'י. עם ways(1) = 1 ו־ways(2) = 2, הספירות הן 1, 2, 3, 5, 8, 13, וזוהי סדרת פיבונאצ'י המוזזת מקום אחד: ways(n) = F(n+1).

מהי סיבוכיות הזמן של טיפוס במדרגות?

הלולאה מלמטה למעלה מבצעת n-2 פעולות חיבור, ולכן זמן הריצה שלה הוא O(n) והיא משתמשת במקום נוסף של O(1). הרקורסיה הרגילה היא אקספוננציאלית: מספר הקריאות שלה גדל פי כ־1.618 בכל צעד ומגיע ל־2269806339, כלומר בערך 2.3 × 10^9, כאשר n = 45. שימוש בזיכרון מטמון מוריד את זמן הריצה של הרקורסיה ל־O(n) ואת המקום שהיא צורכת ל־O(n).

מה ההבדל בין זיכרון מטמון לפתרון מלמטה למעלה?

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

def climbStairs(n):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

n = 3

הפלט הצפוי

Climbing Stairs

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

רקורסיה פשוטה במהלך האחרון

רקורסיה עם זיכרון מטמון

מלמטה למעלה עם שני משתנים

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

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

בעיות דומות