두 번의 순회를 사용하여 그리드에서 최대 포인트 수집


난이도 중급
자주 묻는 질문 아마존 골드만 삭스 구글 하니웰 링크드 인 클립 Yahoo
배열 동적 프로그래밍 매트릭스

문제 정책

“nxm”크기의 행렬이 주어지고두 번의 순회를 사용하여 그리드의 최대 포인트를 올립니다. 셀 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입니다.

두 번의 순회를 사용하여 그리드에서 최대 포인트를 수집하는 알고리즘

순진한 접근

우리는 재귀 먼저 첫 번째 순회를 사용하여 수집 할 수있는 최대 포인트를 찾습니다. 첫 번째 순회 동안 첫 번째 순회 경로로 사용 된 셀을 표시해야합니다. 이제 두 번째 목적지 인 오른쪽 하단에 도달하면 총합을 찾아 그에 따라 답변을 업데이트합니다. 따라서이를 수행하면 첫 번째 및 두 번째 순회의 가능한 모든 조합을 수행했을 것입니다. 그러나이 솔루션은 시간이 기하 급수적으로 복잡하기 때문에 적합하지 않습니다.

효율적인 접근

XNUMX 차 및 XNUMX 차 순회를 동시에 실행하고 동적 프로그래밍. 따라서 우리는 왼쪽 상단과 오른쪽 상단 모서리에서 시작합니다. 그리고 아래 방향으로 다음 행으로 계속 이동하십시오. 그러나 이제는 순회를 동시에 실행하고 있기 때문에. 선택할 수있는 조합은 총 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

자바 코드 두 번의 순회 문제를 사용하여 그리드에서 최대 포인트 수집

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 상태가 있기 때문에 최대에서 우리는 모든 상태를 여행 할 수 있습니다. 이 알고리즘에 대한 다항식 시간 복잡성이 있습니다.

공간 복잡성

O (NM ^ 2), 총 N * M ^ 2 상태가 있기 때문에 최대에서 우리는 모든 상태를 여행 할 수 있습니다. 여기서 DP 어레이는 크기 N x M x M의 3 차원을 가지므로 다항식 공간 복잡성이 달성됩니다.