Հավաքեք առավելագույն միավորները ցանցում `օգտագործելով երկու անցում  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Ֆաբ Goldman Sachs-ը Google HONEYWELL LinkedIn Pinterest Անտաշ անասուն նողկալի արարած
Դասավորություն Դինամիկ ծրագրավորում Matrix

Խնդիրի հայտարարություն  

Մեզ տրված է «nxm» չափի մատրիցա, և մենք պետք է գցանցում ընտրեք առավելագույն կետերը `օգտագործելով երկու անցում: Եթե ​​մենք կանգնած ենք i խցում, j, ապա մենք ունենք երեք տարբերակ ՝ i + 1, j կամ i + 1, j-1 կամ i + 1, j + 1 խուց մտնելու համար: Այսինքն, մենք հաջորդ շարքում կտեղափոխվենք ներքևի ուղղությամբ ընթացիկ բջիջից և ընթացիկ սյունակից կամ հարակից սյուններից: Մենք պետք է սկսենք վերին ձախ անկյունից և անցնենք ձախ ներքևի անկյուն: Երկրորդ անցման համար մենք պետք է վերևի աջ անկյունից անցնենք ներքևի աջ անկյուն:

Օրինակ  

Pin

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-ն են:

Gorանցում առավելագույն միավորներ հավաքելու ալգորիթմ ՝ օգտագործելով երկու անցում  

Միամիտ մոտեցում

Մենք կարող ենք օգտագործել ա ռեկուրսիվ մոտեցում, որտեղ նախ մենք գտնում ենք առավելագույն միավորներ, որոնք կարող են հավաքվել `օգտագործելով առաջին անցումը: Մինչ առաջին անցումը մենք պետք է նշեինք այն բջիջները, որոնք օգտագործվել են որպես առաջին անցման ուղի: Հիմա, երբ հասնենք մեր երկրորդ նպատակակետին, դա աջ ներքևի անկյունն է: Մենք գտնում ենք ընդհանուր գումարը և համապատասխանաբար թարմացնում ենք պատասխանը: Այսպիսով, դա անելով մենք պետք է անցնեինք առաջին և երկրորդ անցումների բոլոր հնարավոր համադրությունները: Բայց քանի որ այս լուծումն ունի էքսպոնենտալ ժամանակի բարդություն, այն հարմար չէ:

Արդյունավետ մոտեցում

Մենք միաժամանակ վարում ենք առաջին և երկրորդ անցումները և օգտագործում դինամիկ ծրագրավորում, Այսպիսով, մենք կսկսենք վերին ձախ և վերին աջ անկյուններից: Եվ շարունակեք շարժվել դեպի հաջորդ շարքը վայրընթաց ուղղությամբ: Բայց հիմա, քանի որ մենք միաժամանակ անցնում ենք անցումներ: Ընդհանուր առմամբ մենք ունենք 9 համադրություն ընտրելու (3-ը `առաջին անցման և 3-ը` երկրորդ անցման համար `դարձնելով այն 3 * 3 = 9 զուգակցում):

Հիմա, քանի որ ենթածրագրերը համընկնում են (այսինքն մենք մի քանի անգամ կլուծենք նույն ենթախնդիրը): Ուստի ցանկալի է պահպանել ենթածրագրերի արդյունքը, որը կնվազեցնի մեր էքսպոնենտալ ժամանակի բարդությունը մինչ բազմանդամի ժամանակի բարդություն:

Կոդ  

C ++ ծածկագիր ցանցի մեջ առավելագույն միավորներ հավաքելու համար `օգտագործելով երկու շրջանցման խնդիր

#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

Java կոդ ցանցի մեջ առավելագույն միավորներ հավաքելու համար `օգտագործելով երկու շրջանցման խնդիր

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (NM ^ 2), քանի որ կան ընդհանուր N * M ^ 2 պետություններ, և քանի որ առավելագույն դեպքում մենք կարող ենք ճանապարհորդել բոլոր նահանգներում: Այս ալգորիթմի համար մենք ունենք բազմանդամ-ժամանակի բարդություն:

Տես նաեւ,
Գտեք k երկարության առավելագույն միջին ենթադասը

Տիեզերական բարդություն

O (NM ^ 2), քանի որ կան ընդհանուր N * M ^ 2 վիճակներ, և քանի որ առավելագույն դեպքում մենք կարող ենք ճանապարհորդել բոլոր նահանգներում: Այստեղ DP զանգվածն ունի N x M x M չափի 3 չափս, ուստի հասնում է բազմանդամ տարածության բարդությանը: