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