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

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“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 차원을 가지므로 다항식 공간 복잡성이 달성됩니다.

균열 시스템 설계 인터뷰
Translate »