किमान पथ बेरीज


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन ब्लूमबर्ग फेसबुक गोल्डमन Sachs Google मायक्रोसॉफ्ट
अरे डायनॅमिक प्रोग्रामिंग

किमान मार्ग बेरीज समस्येमध्ये आम्ही दिले आहेत “ए बी बी” मॅट्रिक्स नॉन-नकारात्मक संख्या असलेल्या आपले कार्य म्हणजे डावीकडून उजवीकडे तळाचा मार्ग शोधणे जे आपल्याला आढळलेल्या मार्गावर येणार्‍या सर्व संख्येचा योग कमी करते.

टीप: आपण कोणत्याही वेळी फक्त खाली किंवा उजवीकडे जाऊ शकता.

उदाहरण

इनपुट

[एक्सएनयूएमएक्स],
[एक्सएनयूएमएक्स],
[1,0,1]

उत्पादन

2

स्पष्टीकरण

कारण ती मार्गावर येते 1→0→0→0→1, जे बेरीज 2 म्हणून कमी करते.

किमान पथ बेरीज

डावीकडून डावीकडे वरुन उजवीकडे जाण्यासाठी ही प्रतिमा दर्शविते

इनपुट

[एक्सएनयूएमएक्स],
[एक्सएनयूएमएक्स],
[4,2,1]

उत्पादन

7

स्पष्टीकरण

कारण ती मार्गावर येते 1→3→1→1→1, जे बेरीज 7 म्हणून कमी करते.

किमान पथ बेरीज

ही प्रतिमा वरच्या डावीकडून डावीकडे उजवीकडे जाण्यासाठीचा मार्ग दर्शवित आहे.

किमान पथ बेरीजसाठी अल्गोरिदम

आता आम्हाला किमान पथ बेरीजचे समस्या विधान समजले. जास्त चर्चा न करता आम्ही या समस्येच्या अंमलबजावणीसाठी वापरल्या जाणार्‍या अल्गोरिदमकडे जाऊ.

  1. मध्ये इनपुट मूल्य मिळवा अॅरे.
  2. लूपसाठी नेस्टेड उघडा आणि दिलेल्या इनपुट अ‍ॅरेच्या सर्व पंक्ती आणि स्तंभ ओलांडल्याशिवाय ते चालवा.
    1. जर मी = = 0 && j = = 0
      • नंतर सुरू ठेवा म्हणजे, हे पुनरावृत्ती सोडा आणि पुढच्या एकावर जा.
    2. अन्यथा i = = 0
      • नंतर अ‍ॅरे [i] [j] = अ‍ॅरे [i] [j] + अरे [i] [j-1];
    3. बाकी जर j = = 0
      • एर [i] [j] = अरर [i] [j] + एर [i-1] [j];
    4. अन्यथा
      • एर [i] [j] = getMin (arr [i-1] [j] + arr [i] [j], Arr [i] [j-1] + Arr [i] [j])
    5. ही मूल्ये गेटमिन फंक्शनमध्ये पास करा जी दोन दरम्यान किमान मूल्य मिळवते.
  3. रिटर्न अ‍ॅरे [पंक्ती -1] [स्तंभ -1];

स्पष्टीकरण

किमान मार्ग बेरीज समस्येमध्ये, आमचे कार्य म्हणजे मॅट्रिक्समधील तो मार्ग शोधणे ज्यायोगे पथात येणा all्या सर्व पूर्णांकांची बेरीज कमी होते, म्हणून फंक्शन घोषित करणे आवश्यक आहे जेथे फंक्शन परिभाषित केले गेले आहे त्या दरम्यानचे सर्वात लहान मूल्य परत मिळविण्यासाठी. त्या फंक्शनला दिलेली दोन व्हॅल्यूज

तर आता आपण लूपसाठी नेस्टेड सुरू करतो, बाह्य लूपला व्हॅल्यू पर्यंत वाढवते (पंक्ती -1) पर्यंत पोहोचते आणि कॉलम -1 पर्यंतची आतील लूप पोहोचली आहे.

स्टेप बाय स्टेप एक्झिक्यूशन

तर आता आपण किमान पाथ योग समस्या समजून घेण्यासाठी एक उदाहरण घेऊ.

इनपुटः {{1,3,4},

{2,0,2},

} 2,0,1}};

आत्ता पुरते,

  • i = 0, j = 0

जर भाग अंमलात आणला आणि तर तो सुरूच राहतो आणि पुढच्या एकावर उडी मारतो.

  • i = 0, j = 1

अन्यथा (i = = 0) अंमलात आणला आणि एर [i] [j] = अरे [i] [j] + एर [i] [j-1]

म्हणजे अरर [0] [1] = 3 + 1 = 4

  • i = 0, j = 2

अन्यथा (i = = 0) अंमलात आणला आणि एर [i] [j] = अरे [i] [j] + एर [i] [j-1]

म्हणजे अरर [०] [२] = अरर [०] [२] + अरर [०] [१] = + +१ =

  • i = 1, j = 0

अन्यथा (j = = 0) अंमलात आणला आणि एर [i] [j] = अरे [i] [j] + एर [i-1] [j]

म्हणजे अरर [०] [२] = अरर [०] [२] + अरर [०] [१] = + +१ =

  • i = 1, j = 1

अन्यथा भाग निष्पादित करतो आणि getMin (arr [i-1] [j] + arr [i] [j], Arr [i] [j-1] + arr [i] [j]) फंक्शन कॉल आहे

आणि getMin (arr [0] [1]) + arr [1] [1], Arr [1] [0] + arr [1] [1]) = (1 + 2, 3 + 2)

जे अररमध्ये सर्वात लहान मूल्य 3 करेल [1] [1] => अरे [1] [1] = 3

  • i = 1, j = 2

अन्यथा भाग निष्पादित करतो आणि getMin (arr [i-1] [j] + arr [i] [j], Arr [i] [j-1] + arr [i] [j]) फंक्शन कॉल आहे

आणि getMin (arr [0] [2]) + arr [1] [2], Arr [1] [1] + arr [1] [2]) = (5 + 2, 3 + 2)

जे अररमध्ये सर्वात लहान मूल्य 5 करेल [1] [2] => अर [1] [2] = 5.

अरे [1] [2] = 5.

  • i = 2, j = 0

अन्यथा (j = = 0) अंमलात आणला आणि एर [i] [j] = अरे [i] [j] + एर [i-1] [j]

म्हणजे अरर [०] [२] = अरर [०] [२] + अरर [०] [१] = + +१ =

अरे [2] [2] = 4.

  • i = 2, j = 1

अन्यथा भाग निष्पादित करतो आणि getMin (arr [i-1] [j] + arr [i] [j], Arr [i] [j-1] + arr [i] [j]) फंक्शन कॉल आहे

आणि getMin (arr [1] [1]) + arr [2] [1], Arr [2] [0] + arr [2] [1]) = (3 + 0, 4 + 0)

जे अररमध्ये सर्वात लहान मूल्य 3 करेल [2] [1] => अर [2] [1] = 3.

अरे [1] [2] = 3.

  • i = 2, j = 2

अन्यथा भाग निष्पादित करतो आणि getMin (arr [i-1] [j] + arr [i] [j], Arr [i] [j-1] + arr [i] [j]) फंक्शन कॉल आहे

आणि getMin (arr [1] [2]) + arr [2] [2], Arr [2] [1] + arr [2] [2]) = (5 + 1, 3 + 1)

जे अररमध्ये सर्वात लहान मूल्य 4 करेल [2] [2] => अर [2] [2] = 5.

अरे [2] [2] = 4.

आणि ते एरर परत करेल [2] [2] जे 4 आहे आणि हे आपले आउटपुट मूल्य आहे जे किमान बेरीज पथ निश्चित करते.

आउटपुट: 4

किमान पथ बेरीजसाठी सी ++ प्रोग्राम

#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

किमान पथ बेरीजसाठी जावा प्रोग्राम

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

किमान पथ बेरीजसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एम * एन) जेथे "M" आणि “एन” किमान पथ बेरीज समस्येमध्ये दिलेल्या मॅट्रिक्समधील पंक्ती आणि स्तंभांची संख्या आहेत.

स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण किमान पथ बेरीजसाठी दृष्टीकोन लागू करताना आम्ही कोणतीही सहाय्यक जागा वापरत नाही.

संदर्भ