סכום נתיב מינימלי


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית בלומברג פייסבוק גולדמן זאקס Google מיקרוסופט
מערך תכנות דינמי

בבעיית סכום הנתיב המינימלי נתנו "A × b" מַטרִיצָה המורכב ממספרים שאינם שליליים. המשימה שלך היא למצוא את הנתיב מלמעלה לשמאל לתחתית ימין אשר ממזער את הסכום המורכב מכל המספרים המגיעים בנתיב שמצאת.

הערה: אתה יכול לנוע רק למטה או ימינה בכל נקודת זמן.

דוגמה

קֶלֶט

[1,0,2],
[2,0,5],
[1,0,1]

תְפוּקָה

2

הסבר

כי זה הולך בדרך 1→0→0→0→1, שממזער את הסכום כ -2.

סכום נתיב מינימלי

תמונה זו מציגה את הנתיב שהולך כדי להגיע משמאל למעלה מימין למטה

קֶלֶט

[1,3,1],
[1,5,1],
[4,2,1]

תְפוּקָה

7

הסבר

כי זה הולך בדרך 1→3→1→1→1, שממזער את הסכום כ -7.

סכום נתיב מינימלי

תמונה זו מציגה את הנתיב שהולך מלמעלה למעלה כדי להגיע מימין למטה.

אלגוריתם לסכום מינימלי של נתיב

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

  1. קבל את ערך הקלט ב- מערך.
  2. פתח לולאה מקוננת והפעל אותה עד שכל השורות והעמודות עוברות במערך הקלט הנתון.
    1. אם i = = 0 && j = = 0
      • ואז המשך, פירושו לעזוב איטרציה זו ולקפוץ אל הבא.
    2. אחרת אם i = = 0
      • ואז מערך [i] [j] = מערך [i] [j] + arr [i] [j-1];
    3. אחרת אם j = = 0
      • arr [i] [j] = arr [i] [j] + arr [i-1] [j];
    4. אחר
      • arr [i] [j] = getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j])
    5. העבירו ערכים אלה לפונקציה getMin המחזירה את הערך המינימלי בין שניים.
  3. מערך החזרה [שורות -1] [עמודות -1];

הסבר

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

אז עכשיו, אנו מתחילים לולאה מקוננת, הופכים את הלולאה החיצונית לקראת הערך (שורה -1) ומגיעים לולאה הפנימית עד לטור -1.

ביצוע שלב אחר שלב

אז בואו ניקח דוגמא להבנת בעיית סכום מינימלי של נתיב,

קלט: {{1,3,4},

{2,0,2},

{2,0,1}};

לעת עתה,

  • i = 0, j = 0

אם חלק יבוצע וזה ימשיך ויקפוץ לחלק הבא.

  • i = 0, j = 1

אחרת אם (i = = 0) מבצע ו arr [i] [j] = arr [i] [j] + arr [i] [j-1]

פירושו arr [0] [1] = 3 + 1 = 4

  • i = 0, j = 2

אחרת אם (i = = 0) מבצע ו arr [i] [j] = arr [i] [j] + arr [i] [j-1]

פירושו arr [0] [2] = arr [0] [2] + arr [0] [1] = 4 +1 = 5

  • i = 1, j = 0

אחרת אם (j = = 0) מבצע ו arr [i] [j] = arr [i] [j] + arr [i-1] [j]

פירושו arr [1] [0] = arr [1] [0] + arr [0] [0] = 2 +1 = 3

  • i = 1, j = 1

חלק אחר מבצע ופונקציית getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) היא call

ו- getMin (arr [0] [1]) + arr [1] [1], arr [1] [0] + arr [1] [1]) = (1 + 2, 3 + 2)

שיחזיר הערך הקטן ביותר הוא 3 ב arr [1] [1] => arr [1] [1] = 3

  • i = 1, j = 2

חלק אחר מבצע ופונקציית getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) היא call

ו- getMin (arr [0] [2]) + arr [1] [2], arr [1] [1] + arr [1] [2]) = (5 + 2, 3 + 2)

שיחזיר הערך הקטן ביותר הוא 5 ב arr [1] [2] => arr [1] [2] = 5.

arr [1] [2] = 5.

  • i = 2, j = 0

אחרת אם (j = = 0) מבצע ו arr [i] [j] = arr [i] [j] + arr [i-1] [j]

פירושו arr [2] [0] = arr [2] [0] + arr [1] [0] = 2 +2 = 4

arr [2] [2] = 4.

  • i = 2, j = 1

חלק אחר מבצע ופונקציית getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) היא call

ו- getMin (arr [1] [1]) + arr [2] [1], arr [2] [0] + arr [2] [1]) = (3 + 0, 4 + 0)

שיחזיר הערך הקטן ביותר הוא 3 ב arr [2] [1] => arr [2] [1] = 3.

arr [1] [2] = 3.

  • i = 2, j = 2

חלק אחר מבצע ופונקציית getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) היא call

ו- getMin (arr [1] [2]) + arr [2] [2], arr [2] [1] + arr [2] [2]) = (5 + 1, 3 + 1)

שיחזיר הערך הקטן ביותר הוא 4 ב arr [2] [2] => arr [2] [2] = 5.

arr [2] [2] = 4.

והוא יחזיר את ה- arr [2] [2] שהוא 4 וזה ערך הפלט שלנו שמגדיר את נתיב הסכום המינימלי.

תפוקה: 4

תכנית C ++ לסכום נתיב מינימלי

#include<iostream>
using namespace std;

int getMin(int val1, int val2)
{
    return val1 < val2 ? val1 : val2;
}
int getMinimumSum(int arr[3][3])
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i==0 && j == 0)
            {
                continue;
            }
            else if(i==0)
            {
                arr[i][j] = arr[i][j] + arr[i][j-1];
            }
            else if(j==0)
            {
                arr[i][j] = arr[i][j] + arr[i-1][j];
            }
            else
            {
                arr[i][j] = getMin(arr[i-1][j]+arr[i][j], arr[i][j-1]+arr[i][j]);
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputArray[3][3] = {{1,3,4},
                            {2,0,2},
                            {2,0,1}};
                            
    cout<<"Length of minimum path sum: "<<getMinimumSum(inputArray);
    return 0;
}
Length of minimum path sum: 4

תוכנית Java לסכום מינימלי של נתיב

class MinimumPathSum {
  private static int getMin(int val1, int val2) {
    return val1<val2 ? val1 : val2;
  }
  private static int getMinimumSum(int[][] arr) {
    for (int i = 0; i<arr.length; i++) {
      for (int j = 0; j<arr[i].length; j++) {
        if (i == 0 && j == 0) {
          continue;
        } else if (i == 0) {
          arr[i][j] = arr[i][j] + arr[i][j - 1];
        } else if (j == 0) {
          arr[i][j] = arr[i][j] + arr[i - 1][j];
        } else {
          arr[i][j] = getMin(arr[i - 1][j] + arr[i][j], arr[i][j - 1] + arr[i][j]);
        }
      }
    }
    int r = arr.length - 1;
    int c = arr[0].length - 1;
    return arr[r][c];
  }
  public static void main(String[] args) {
    int[][] inputArray = {{1, 3, 4},
                {2, 0, 2},
                {2, 0, 1}};

    System.out.println("Length of minimum path sum: " + getMinimumSum(inputArray));
  }
}
Length of minimum path sum: 4

ניתוח מורכבות עבור סכום נתיב מינימלי

מורכבות זמן

O (m * n) איפה "M" ו "N" הם מספר השורות והעמודות במטריצה ​​הנתונות בבעיית סכום הנתיב המינימלי.

מורכבות בחלל

O (1) מכיוון שאנו לא משתמשים בשום שטח עזר בזמן שאנחנו מיישמים את הגישה בסכום מינימלי של נתיב.

הפניות