איך להתחיל מאחור ולסיים לפני כולם - אתגר תכנותי בשלושה חלקים

לפעמים בעיות תכנות נראות פשוטות במבט ראשון — ואז מצליחות להפתיע אותנו. אחת הדוגמאות לכך היא בעיית ה־Jump Game מ־LeetCode.

❓ תיאור הבעיה

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

מתחילים באינדקס הראשון (index = 0), והמטרה היא להגיע לאינדקס האחרון של המערך.

אם ניתן להגיע אליו — יש להחזיר True, אחרת False.

דוגמאות:

nums = [2,3,1,1,4]  ➞  True

• כי ניתן לקפוץ מ-0 ל-1, ומשם 3 צעדים עד הסוף.

nums = [3,2,1,0,4]  ➞  False

• איך שתנסה, בסוף תתקע באינדקס 3 עם 0 צעדים.

ניסיון ראשון: כח גס

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

def can_jump_from(index, nums):
    if index >= len(nums) - 1:
        return True

    max_jump = nums[index]
    for step in range(1, max_jump + 1):
        if can_jump_from(index + step, nums):
            return True

    return False

def can_jump(nums):
    return can_jump_from(0, nums)

נבדוק:

# Test cases
print(can_jump([2, 0, 0])) # True
print(can_jump([2,3,1,1,4])) # True
print(can_jump([3,2,1,0,4])) # False
print(can_jump([1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9])) # True
print(can_jump([1])) # True
print(can_jump([])) # True

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

תכנות דינמי: חכם, אבל לא מספיק

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

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

קוד התכנות הדינמי להלן מיישם את הגישה:

def can_jump(nums):
    n = len(nums)
    dp = [False] * n
    dp[-1] = True

    for i in range(n - 2, -1, -1):
        max_jump = min(i + nums[i], n - 1)
        for j in range(i + 1, max_jump + 1):
            if dp[j]:
                dp[i] = True
                break

    return dp[0]

סיבוכיות זמן: O(N^2)

סיבוכיות זיכרון: O(N)

שיפור מאוד משמעותי אבל עדיין אפשר למצוא פתרון יעיל יותר.

פתרון חמדני במסגרתו חשיבה הפוכה מאפשר התקדמות מהירה

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

האלגוריתם סורק את המערך מהסוף להתחלה, ומעדכן בכל שלב את האינדקס השמאלי ביותר שממנו ניתן להגיע לסוף. אם אחרי הסריקה הגענו למסקנה שניתן להגיע לסוף מאינדקס 0, אז ברור שניתן להשלים את המשימה.

הקוד הבא מיישם את הפתרון החמדני + חשיבה הפוכה 🔄:

def can_jump(nums):
    len_nums = len(nums)

    if len_nums <= 1:
        return True

    target = len_nums - 1

    for i in range(len_nums - 2, -1, -1):
        if i + nums[i] >= target:
            target = i

    return target == 0

יתרונות:

• סיבוכיות זמן: O(N)
• סיבוכיות זיכרון: O(1)
• פשוט, יעיל, ומהיר 🚀.

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

לסיכום

ה־Jump Game היא לא רק אתגר באלגוריתמים — היא שיעור בחשיבה, אז מה למדנו?

• להתחיל פשוט — ואז להשתפר
• לא להסתפק בפתרונות לא יעילים
• להבין מתי ואיך לחשוב הפוך
• להעדיף פתרונות ברורים ויעילים

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

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

פתרון בעיות אופטימיזיציה באמצעות אלגוריתם חמדן

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

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

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

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

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