दोन ट्रॅव्हर्सलचा वापर करून ग्रीडमध्ये जास्तीत जास्त गुण गोळा करा


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

समस्या विधान

आपल्याला “एनएक्सएम” आकाराचे मॅट्रिक्स दिले आहेत आणि आपल्याला सीदोन ट्रॅव्हर्सलचा वापर करून ग्रीडमध्ये जास्तीत जास्त बिंदू निवडा. जर आपण सेल i, j वर उभे असाल तर आपल्याकडे सेल i + 1, j किंवा i + 1, j-1or i + 1, j + 1 वर जाण्यासाठी तीन पर्याय आहेत. म्हणजेच आम्ही चालू सेल वरुन खाली असलेल्या दिशेच्या पुढच्या ओळीवर आणि सद्य कॉलम वर किंवा समीप स्तंभांकडे जाऊ. आपल्याला वरच्या डाव्या कोप from्यातून प्रारंभ करणे आणि डाव्या तळाशी कोपर्यात जाण्याची आवश्यकता आहे. दुसर्‍या ट्रॅव्हर्सलसाठी, आम्हाला वरच्या उजव्या कोप from्यातून खालच्या उजव्या कोपर्यात जाण्याची आवश्यकता आहे.

उदाहरण

Size of matrix = 3 x 3

Matrix

10 2 20

9 10 5

10 100 20
75

स्पष्टीकरणः प्रथम ट्रॅव्हर्शल मूव्ह्स 10-> 10-> 10 वरून आहेत, एकूण 30 गुण बनतात.

द्वितीय आक्रमक यानुसार 20-> 5-> 20 आहेत, अशा प्रकारे एकूण 20 + 5 + 20 = 45 गुण आहेत. येथे आम्ही 100 निवडत नाही तेव्हापासून आम्ही दोन्ही प्रकरणांमध्ये (प्रथम आणि द्वितीय आक्रमणे) आमच्या गंतव्यस्थानावर पोहोचू शकलो नसतो. अशाप्रकारे आम्ही गोळा करू शकलेले जास्तीत जास्त गुण 75 आहेत.

दोन ट्रॅव्हर्सलचा वापर करून ग्रीडमध्ये जास्तीत जास्त गुण गोळा करण्यासाठी अल्गोरिदम

भोळे दृष्टिकोन

आम्ही एक वापरू शकतो रिकर्सिव अप्रोच, जिथे प्रथम आम्हाला जास्तीत जास्त बिंदू आढळतात जे प्रथम ट्रॅव्हर्सलचा वापर करून गोळा केले जाऊ शकतात. प्रथम आक्रमक असताना आम्ही प्रथम आक्रमणाकरिता पथ म्हणून वापरले गेलेले सेल चिन्हांकित केले पाहिजेत. आता जेव्हा आपण आमच्या दुसर्‍या गंतव्यस्थानावर पोहोचतो तेव्हा उजवा तळाचा कोपरा आहे. आम्ही एकूण बेरीज शोधतो आणि त्यानुसार उत्तर अद्यतनित करतो. तर, हे करत असताना आम्ही प्रथम आणि द्वितीय ट्रॅव्हर्सलच्या सर्व शक्य संयोजनांमध्ये गेलो असतो. परंतु या सोल्यूशनमध्ये घाईघाईची वेळ गुंतागुंत असल्याने ते योग्य नाही.

कार्यक्षम दृष्टीकोन

आम्ही एकाच वेळी प्रथम आणि द्वितीय ट्रॅव्हर्सल चालवितो आणि वापरतो डायनॅमिक प्रोग्रामिंग. तर, आम्ही डावीकडील आणि डाव्या कोप from्यापासून सुरवात करू. आणि पुढील पंक्तीकडे खाली दिशेने जा. परंतु आता आम्ही एकाचवेळी ट्रॅव्हर्सेल्स चालवित आहोत. आमच्याकडे निवडण्यासाठी एकूण 9 संयोग आहेत (प्रथम ट्रॅव्हर्सलसाठी 3 आणि दुसर्‍या ट्रॅव्हर्सलसाठी 3, त्यास 3 * 3 = 9 संयोग बनवून).

आता सबप्रोब्लम्स आच्छादित होत आहेत (म्हणजे आम्ही तीच सबप्रॉब्लम अनेक वेळा सोडवत आहोत). अशा प्रकारे सबप्रोब्लम्सचा निकाल संग्रहित ठेवण्याचा सल्ला दिला जातो ज्यामुळे आपली बहुतेक वेळेची जटिलता बहुतेक वेळेची गुंतागुंत कमी होईल.

कोड

सी ++ कोड दोन ट्रॅव्हर्सर समस्या वापरून ग्रीडमध्ये जास्तीत जास्त गुण गोळा करण्यासाठी

#include<bits/stdc++.h>
using namespace std;

int dir[3] = {-1, 0, 1};
bool isValid(int x, int y1, int y2, int rowSize, int colSize){
    return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
}

int collectMaxPointsInGridUsingTwoTraversals(vector<vector<int>> &matrix, vector<vector<vector<int>>> &dp, int x, int y1, int y2, int rowSize, int colSize)
{
    if(!isValid(x, y1, y2, rowSize, colSize))
        return INT_MIN;
    if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
        return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
    if (x == rowSize-1)
        return INT_MIN;

    if (dp[x][y1][y2] != -1)
        return dp[x][y1][y2];

    int ans = INT_MIN;
    int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);

    for(int i = 0; i < 3; i++){
        for(int j=0;j<3;j++){
            ans = max(ans, currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize));
        }
    }
    return (dp[x][y1][y2] = ans);
}

int main()
{
    int rowSize, colSize;
    cin>>rowSize>>colSize;
    vector<vector<int>> matrix(rowSize, vector<int>(colSize));
    vector<vector<vector<int>>> dp(rowSize, vector<vector<int>>(colSize, vector<int>(colSize, -1)));
    for(int i=0;i<rowSize;i++){
        for(int j=0;j<colSize;j++)
            cin>>matrix[i][j];
    }
    cout << "Maximum collection is " <<collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
    return 0;
}
3 3
10 1 20
5 10 5
10 100 20
Maximum collection is 75

जावा कोड दोन ट्रॅव्हर्सर समस्या वापरून ग्रीडमध्ये जास्तीत जास्त गुण गोळा करण्यासाठी

import java.util.*;

class Main{
    
    static int dir[] = {-1, 0, 1};
    static boolean isValid(int x, int y1, int y2, int rowSize, int colSize){
        return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
    }
    
    static int collectMaxPointsInGridUsingTwoTraversals(int[][] matrix, int[][][] dp, int x, int y1, int y2, int rowSize, int colSize)
    {
        if(!isValid(x, y1, y2, rowSize, colSize))
            return Integer.MIN_VALUE;
        if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
            return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
        if (x == rowSize-1)
            return Integer.MIN_VALUE;
    
        if (dp[x][y1][y2] != -1)
            return dp[x][y1][y2];
    
        int ans = Integer.MIN_VALUE;
        int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
    
        for(int i = 0; i < 3; i++){
            for(int j=0;j<3;j++){
                int tmp = currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize);
                ans = Math.max(ans, tmp);
            }
        }
        return (dp[x][y1][y2] = ans);
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int rowSize = sc.nextInt();
        int colSize = sc.nextInt();
        int matrix[][] = new int[rowSize][colSize];
        int dp[][][] = new int[rowSize][colSize][colSize];
        for(int i=0;i<rowSize;i++){
            for(int j=0;j<colSize;j++){
                matrix[i][j] = sc.nextInt();
                for(int k=0;k<colSize;k++)
                    dp[i][j][k] = -1;
            }
        }
        int answer = collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
        System.out.println("Maximum collection is "+answer);
    }
}
3 3
10 1 20
5 10 5
10 100 20
Maximum collection is 75

गुंतागुंत विश्लेषण

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

ओ (एनएम ^ 2), एकूण एन * एम ^ 2 राज्ये असल्याने आणि जास्तीत जास्त आम्ही सर्व राज्ये प्रवास करू शकतो. आमच्याकडे या अल्गोरिदमसाठी बहु-वेळची गुंतागुंत आहे.

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

ओ (एनएम ^ 2), एकूण एन * एम ^ 2 राज्ये असल्याने आणि जास्तीत जास्त आम्ही सर्व राज्ये प्रवास करू शकतो. येथे डीपी अ‍ॅरेला एन एक्स एम एक्स एम एम आकाराचे 3 परिमाण आहेत, अशा प्रकारे बहुपदी जागेची जटिलता प्राप्त केली जाते.