חידה תכנותית : רבות הדרכים

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

לדוגמה:

Input: width = 5, height = 4
Output: 35

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

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

OK, אבל איך פותרים את הבעיה באמצעות תכנות דינאמי?

עבור כל תא במיקום (i, j) העז יכולה להגיע מהתא שמעליו (i-1, j) או מהתא שמשמאלו (i, j-1). לכן, מספר הדרכים להגיע לתא (i, j) היא סכום הדרכים להגעה לתא שמעל ולתא שמשמאל.

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

# Create a 2D DP table initialized with zeros.
dp = [[0] * width for _ in range(height)]

מילוי הטבלה dp

1. אל התא ההתחלתי (0, 0) יש רק דרך אחת להגיע.

   # Starting cell: Only one way to be here.
   dp[0][0] = 1

2. מילוי השורה הראשונה והעמודה הראשונה: יש דרך אחת בלבד להגיע לכל תא בשורה הראשונה (תנועה ימינה בלבד) ויש דרך אחת בלבד להגיע לכל תא בעמודה הראשונה (תנועה למטה בלבד).

   # Initialize the left-most column (the only way is downs).
   for x in range(1, width):
       dp[0][x] = 1
       
   # Initialize the top-most row (the only way is right).
   for x in range(1, width):
       dp[0][x] = 1

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

   # Fill the rest of the DP table.
   for y in range(1, height):
       for x in range(1, width):
           dp[y][x] = dp[y-1][x] + dp[y][x-1]

4. התשובה נמצאת בתא האחרון ואותו תחזיר הפונקציה:

   # The bottom-right cell contains the answer.
   return dp[height-1][width-1]
   

הקוד להלן מממש את הפתרון:

def find_unique_paths(height, width):
    # Sanitize the input to ensure valid grid dimensions.
    if height < 1 or width < 1:
        return 0

    # Create a 2D DP table initialized with zeros.
    dp = [[0] * width for _ in range(height)]
    
    # Starting cell: Only one way to be here.
    dp[0][0] = 1

    # Initialize the left-most column (the only way is down).
    for y in range(1, height):
        dp[y][0] = 1
    
    # Initialize the top-most row (the only way is right).
    for x in range(1, width):
        dp[0][x] = 1

    # Fill the rest of the DP table.
    for y in range(1, height):
        for x in range(1, width):
            dp[y][x] = dp[y-1][x] + dp[y][x-1]
    
    # The bottom-right cell contains the answer.
    return dp[height-1][width-1]

נבדוק:

# Test cases
print(find_unique_paths(5, 4))  # 35
print(find_unique_paths(4, 5))  # 35
print(find_unique_paths(3, 1))  # 1
print(find_unique_paths(1, 3))  # 1
print(find_unique_paths(1, 1))  # 1
print(find_unique_paths(0, 1))  # 0

הערכת יעילות

• כיוון שכל תא בטבלה מחושב פעם אחת בלבד סיבוכיות הזמן הנדרשת היא O(M*N).

• לצורך אחסון טבלת DP בממדים m*n נדרש מקום נוסף בזכרון שהוא O(M*N).

שיפור אופציונלי: אופטימיזציה של יעילות המרחב

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

def find_unique_paths(height, width):
    if height < 1 or width < 1:
        return 0
      
    # DP table of only 1 row with all cells continuing ones.
    dp = [1] * width
    
    # For each  row update the current dp row.
    for _ in range(1, height):
        for j in range(1, width):
            dp[j] += dp[j - 1]
    
    return dp[-1]

מי ייתן וינעם לך קידודך.

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

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

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

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

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

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

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