Climbing Stairs
אתה עומד בתחתית גרם מדרגות עם n מדרגות. בכל צעד מטפסים מדרגה אחת או שתיים. שתי דרכי טיפוס נחשבות שונות כאשר רצפי הצעדים שלהן שונים, לכן 1, 2 ו־2, 1 הן שתי דרכים. הפונקציה שלך מקבלת את n ומחזירה את מספר הדרכים השונות להגיע לראש.
פונקציה
- 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.
+13 בדיקות נסתרות בשליחה
שאלת המשך
מה אם חלק מהמדרגות שבורות וייתכן שלעולם לא תעמוד עליהן? איך נוסחת הנסיגה משתנה, ומהו מספר הדרכים להגיע למדרגה שבורה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התבונן במהלך האחרון בכל טיפוס אל שלב
n. היכן יכולת לעמוד ממש לפניו?כל טיפוס אל מדרגה
nמסתיים בצעד של מדרגה אחת ממדרגהn-1או בצעד של שתי מדרגות ממדרגהn-2, לעולם לא בשניהם. לכן מספר האפשרויות עבורnהוא מספר האפשרויות עבורn-1ועוד מספר האפשרויות עבורn-2.התחילו מהספירות עבור צעד אחד (דרך אחת) ושני צעדים (2 דרכים), והמשיכו כלפי מעלה. תמיד תצטרכו רק את שתי הספירות האחרונות, וכל ספירה חדשה היא הסכום שלהן.
פתרון
אי אפשר לרשום כל טיפוס: בגרם מדרגות בן 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#.
שאלות נפוצות4
למה טיפוס במדרגות הוא בעיית פיבונאצ'י?
כל טיפוס אל מדרגה 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). הלולאה גם מאפשרת לוותר על הטבלה ולהחזיק שני מספרים.
איך פותרים את בעיית הטיפוס במדרגות בצעדים של 1, 2 או 3?
שוב חלקו את הטיפוסים לפי הצעד האחרון שלהם: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). התחילו מ־ways(0) = 1 (הטיפוס הריק), ways(1) = 1 ו־ways(2) = 2, ושמרו את שלושת הספירות האחרונות במקום שתיים. זמן הריצה נשאר O(n) והזיכרון O(1).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def climbStairs(n):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
n = 3
צפוי
3