Собрать максимальное количество точек в сетке с помощью двух обходов


Сложный уровень средний
Часто спрашивают в Амазонка Потрясающий Goldman Sachs Google Honeywell LinkedIn Pinterest Yahoo
массив Динамическое программирование матрица

Постановка задачи

Нам дана матрица размера «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.

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

Наивный подход

Мы можем использовать рекурсивный подход, где сначала мы находим максимальное количество точек, которые можно собрать с помощью первого обхода. Во время первого обхода мы должны были отметить ячейки, которые использовались в качестве пути для первого обхода. Теперь, когда мы достигаем второго пункта назначения, это правый нижний угол. Находим общую сумму и соответственно обновляем ответ. Итак, делая это, мы бы прошли все возможные комбинации первого и второго обхода. Но поскольку это решение имеет экспоненциальную временную сложность, оно не подходит.

Эффективный подход

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

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

Сложность времени

О (НМ ^ 2), так как имеется всего N * M ^ 2 состояний, и так как на max мы можем путешествовать по всем состояниям. У нас есть полиномиальная сложность для этого алгоритма.

Космическая сложность

О (НМ ^ 2), так как имеется всего N * M ^ 2 состояний, и так как на max мы можем путешествовать по всем состояниям. Здесь массив DP имеет 3 измерения размером N x M x M, таким образом достигается сложность полиномиального пространства.