Leetcode 하드 동태 기획 문제 풀이

이트코드는 매우 인기 있는 면접 준비 사이트로 뛰어난 데이터 구조와 문제 알고리즘을 가지고 있어SDE/SWE 면접을 준비할 수 있다.
이 글에서 우리는 리코더Cherry Pickup II 중의 평가하기 어려운 동적 기획 문제와 주어진 문제가 동적 기획 문제인지 탐욕스러운 방법으로 해결할 수 있는지 연구할 것이다.
앵두밭을 대표하는 xcols 행렬 격자를 정하세요.그물의 각 칸은 수집할 수 있는 체리의 수를 나타낸다.
너는 두 개의 로봇이 너를 위해 체리를 수집할 수 있다. 로봇 #1은 그물의 왼쪽 상단(0,0)에 있고, 로봇 #2는 그물의 오른쪽 상단(0,cols-1)에 있다.
다음 규칙에 따라 두 로봇을 사용하여 체리가 수집한 최대 수량을 되돌려준다.
로봇은 한 단원(i, j)에서 단원(i+1, j-1), (i+1, j) 또는 (i+1, j+1)으로 이동할 수 있다.

어떤 로봇이 하나의 세포를 지나갈 때 모든 앵두를 주우면 세포는 공세포로 변한다(0).

두 로봇이 모두 같은 감방에 있을 때 한 로봇만 체리를 먹는다.

두 로봇은 언제든지 그물을 옮길 수 없다.

두 로봇은 모두 그물의 최하층에 도달해야 한다.

제한 사항:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100 

지금 답을 생각해 보면 우리가 얻을 수 있는 이 문제에 대한 동태적인 기획이 필요한 가장 큰 힌트는'최대 앵두수로 돌아가기'라는 줄이다. 이것은 문제를 최적화하는 단서이다.문제를 최적화하려면 수중의 상황/문제를 최대화하거나 최소화해야 한다.
비록 당신이 나에게 물어볼 수 있지만, 우리는 어떻게 해야만 이 문제를 다른 최적화 알고리즘 기술로 해결할 수 있는지 확보할 수 있다. 즉, 동적 계획에 비해 탐욕스러운 알고리즘이다.
당신이 모르는 상황에서 욕심 알고리즘의 목표는 한 걸음 한 걸음 국부적 최우선(욕심 방법)을 사용하여 최우선성을 찾는 것이고, 동적 기획의 목표는 주어진 환경에서 전체적인 최우선을 찾는 것이다.
간단한 예를 들어 의심을 없애는 데 도움을 줄 수 있다.

만약에 우리가 한 걸음 한 걸음 국부적으로 가장 좋은 단원을 선택한다면 우리는 계속 값이 10인 단원을 선택할 것이다. 두 로봇은 각자의 줄을 따라 아래로 이동하고 대각선을 따라 이동하지 않으며 값이 100인 단원에 도달하지 않기 때문에 가장 좋은 결과를 놓쳤다.
예시2에서도 탐욕법의 실패를 나타낸다. 만약에 우리가 국부 최적 단원을 선택한다면 로봇1은 초기 위치에서 두 번째 줄의 값이 2인 단원으로 이동하지만 값이 0인 단원이 아니라 세 번째 줄과 네 번째 줄의 값이 각각 9와 5인 단원에 도달할 수 없기 때문이다.

Thus, a good way to decide whether a problem requires greedy or DP, is to come up with a logic as to why a locally optimal method may or may not fail for the given situation.

이제 DP 솔루션을 고려할 때 다음 사항을 고려해야 합니다.

두 로봇은 모두 맨 밑에 있는 줄에 도달해야 한다. 한 걸음 한 걸음 아래로 이동하면 우리는 로봇을 동시에 이동할 수 있고 이것은 우리의 답안에 영향을 주지 않는다.

행렬 크기의 제한이 매우 낮기 때문에 O(n^3) 풀이라도 시간 제한을 주지 않을 수 있습니다.

과도한 조건과 통용성을 잃는 것을 방지하기 위해 우리는 로봇1이 전체 이동 과정에서 로봇2의 왼쪽에 있는 같은 단원에 위치하는 것을 고려할 것이다.로봇2를 로봇1의 왼쪽으로 이동하려면 로봇이 현재 이동하기 전에 같은 칸이나 앞줄의 인접한 칸을 한 번 교차시켜야 한다.따라서 우리는 로봇 2가 로봇 1(내가 로봇 1을 오른쪽으로 움직이게 하고 로봇 2를 왼쪽으로 움직이게 하는 것)을 통과하게 하는 것이 아니라 로봇 1을 오른쪽으로 움직일 수 있다.이것은 우리의 답안에 영향을 주지 않을 뿐만 아니라, 코드를 작성할 때 더욱 간결해질 것이다.

현재 DP를 계산할 때 우리의 답은 3개의 상태/변수에 달려 있다. 우리의 현재 줄 r, 로봇 1 현재 열 c1과 로봇 2 현재 열 c2이다.그래서 우리의 출발점은
dp[0][0][#cols-1]
어떤 상태든지 dp[i][j][k]를 보면 로봇이 매트릭스에 남아 교차하지 않고 로봇 1이 로봇 2의 왼쪽에 있으면 최대 9가지 이동 방식(로봇마다 3가지 이동 방식이 있다)이 있을 수 있다.
이제 DP[0][0][#cols-1]에서 마지막 줄로 이동하는 표준 DP를 작성해야 합니다.CPP에 상향식 DP 솔루션이 있습니다.

class Solution {
public:
    int rows, cols;
    int cherryPickup(vector<vector<int>>& grid) {
        rows = (int)grid.size();
        cols = (int)grid[0].size();

        // initializing a 3D array dp
        vector<vector<vector<int>>> dp(rows, vector<vector<int>> (cols, vector<int>(cols, -1)));
        int ans = solve(dp, 0, 0, cols - 1, grid);
        return ans;
    }


    int solve(vector<vector<vector<int>>> &dp, int r, int c1, int c2, vector<vector<int>> &grid) {
        if(r >= rows) return 0;
        if(c1 < 0 or c2 < 0 or c1 >= cols or c2 >= cols or c1 > c2) return 0; 
        if(dp[r][c1][c2] != -1) return dp[r][c1][c2];

        int cur= grid[r][c1];
        if(c1 != c2) cur+= grid[r][c2];

        int mx = 0;
        mx = max({mx, solve(dp, r + 1, c1, c2, grid), 
solve(dp, r + 1, c1, c2 - 1, grid), solve(dp, r + 1, c1 + 1, c2 - 1, grid), 
solve(dp, r + 1, c1 + 1, c2, grid)});

        if(c1)
            mx= max({mx, solve(dp, r + 1, c1 - 1, c2, grid), 
solve(dp, r+1, c1-1, c2-1, grid)});

        if(c2 + 1 < cols)
            mx= max({mx, solve(dp, r + 1, c1, c2 + 1, grid), 
solve(dp, r + 1, c1 + 1, c2 + 1, grid)});

        if(c1 and c2 + 1 < cols)
            mx= max(mx, solve(dp, r + 1, c1 - 1, c2 + 1, grid));


        return dp[r][c1][c2] = mx + cur;
    }
};

읽어주셔서 감사합니다!만약 당신이 이 글을 좋아한다면, 멋진 반응과 평론으로 당신의 사랑과 지지를 표현하세요.