Съберете максимални точки в мрежа, като използвате две ходове  


Ниво на трудност M
Често задавани в Амазонка Fab Goldman Sachs Google Honeywell LinkedIn Pinterest Yahoo
Array Динамично програмиране матрица

Декларация за проблема  

Дадена ни е матрица с размер „nxm“ и трябва да cИзберете максимални точки в мрежа, като използвате две ходове. Ако стоим в клетка i, j, тогава имаме три възможности да преминем към клетка i + 1, j или i + 1, j-1 или i + 1, j + 1. Това означава, че ще преминем към следващия ред в посока надолу от текущата клетка и към текущата колона или към съседни колони. Трябва да започнем от горния ляв ъгъл и да отидем до левия долен ъгъл. За второто обхождане трябва да преминем от горния десен ъгъл до долния десен ъгъл.

Пример  

щифт

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.

Алгоритъм за събиране на максимални точки в решетка с помощта на два хода  

Наивен подход

Можем да използваме a рекурсивни подход, където първо намираме максималните точки, които могат да бъдат събрани при първото обхождане. Докато първото обхождане трябваше да маркираме клетките, които са били използвани като път за първото обръщане. Сега, когато стигнем до втората дестинация, това е десният долен ъгъл Намираме общата сума и съответно актуализираме отговора. Така че, правейки това, щяхме да преминем през всички възможни комбинации от първо и второ обхождане. Но тъй като това решение има експоненциална времева сложност, то не е подходящо.

Ефективен подход

Изпълняваме едновременно и използваме първи и втори ход динамично програмиране. И така, ще започнем от горния ляв и горния десен ъгъл. И продължете към следващия ред в посока надолу. Но сега, тъй като изпълняваме ходове едновременно. Имаме общо 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

Анализ на сложността  

Сложност във времето

O (NM ^ 2), тъй като има общо N * M ^ 2 състояния и тъй като при max можем да пътуваме по всички състояния. Ние имаме полиномиална времева сложност за този алгоритъм.

Вижте също
Намерете максимален среден подмасив от k дължина

Сложност на пространството

O (NM ^ 2), тъй като има общо N * M ^ 2 състояния и тъй като при max можем да пътуваме по всички състояния. Тук DP масивът има 3 измерения с размер N x M x M, като по този начин се постига сложност на полиномното пространство.