[LeetCode] 1463. Cherry Pickup II

https://leetcode.com/problems/cherry-pickup-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Cherry Pickup II

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

• Robot #1 is located at the top-left corner (0, 0), and
• Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

• From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
• When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
• When both robots stay in the same cell, only one takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in grid.

m x n의 2차원 배열 grid가 주어진다.

Grid[i][j]에는 수확할 수 있는 체리가 저장되어 있다.

 

당신은 두 로봇이 있고, 이들로 수확한다:

• 로봇 1은 [0, 0]에서 시작한다.
• 로봇 2는 [0, m-1]에서 시작한다.

두 로봇으로 수확할 수 있는 최대값을 구하시오.

• 로봇은 (I, j)에서 (I, j-1), (I, j), (I, j+1)로 이동할 수 있다.
• 로봇은 그 자리의 체리를 수확한다.
• 같은 셀에 가면, 둘 중 하나만 수확한다.
• 수확하고 나서는 더 수확할 수 없다.
• 맨 아래 행으로 도착하면 끝이다.

 

풀이

Dp[i][j][k] = i를 행, j를 로봇 1의 열, k를 로봇 2의 열로 한 최대 체리수로 한다. 처음에는 -1로 초기화한다.

Dp[0][0][m-1]에 grid[0][0] + grid[0][m-1]로, 시작 값을 넣어준다.

 

Dp[i][j][k](i행 j열, k열)에서 앞의 가능한 최대의 수를 찾는다. 

Dp[i-1][max(0, j-1)][max(0, k-1) ~ Dp[i-1][min(m-1, j+1)][min(m-1, k+1)]에서 가장 얻을 수 있는 큰 값을 구한다.

만약 이 값이 -1이라면, 유효하지 않은 이동이므로 건너뛰고, 아니라면 이 값에 grid[i][j] + grid[i][k]를 더한다.

만약 j == k인 경우, 둘 중 하나만 주우므로 grid[i][j]를 하나 빼준다.

 

Dp[n-1][0][0] ~ dp[n-1][m-1][m-1]에서 가장 큰 값을 반환한다.

 

 

코드

C++

class Solution {
    int n;
    int m;
    vector<vector<vector<int>>> dp;
public:
    int getMax(int row, int col1, int col2) {
        int maxNum = -1;

        for(int i = max(0, col1-1); i <= min(m-1, col1+1); i++) {
            for(int j = max(0, col2-1); j <= min(m-1, col2+1); j++) {
                maxNum = max(maxNum, dp[row-1][i][j]);
            }
        }
        return maxNum;
    }

    int cherryPickup(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        dp = vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(m, -1)));

        dp[0][0][m-1] = grid[0][0] + grid[0][m-1];

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < m; k++) {
                    int prev = getMax(i, j, k);
                    if(prev == -1) continue;
                    dp[i][j][k] = prev + grid[i][j] + grid[i][k];
                    if(j == k) dp[i][j][k] -= grid[i][j];
                }
            }
        }

        int ans = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                ans = max(ans, dp[n-1][i][j]);
            }
        }

        // for(int i = 0; i < n; i++) {
        //     for(int j = 0; j < m; j++) {
        //         for(int k = 0; k < m; k++) {
        //             cout << "i, j, k: " << i << " " << j << " " << k << " " << dp[i][j][k] <<"|";
        //         }
        //     }
        //     cout << endl;
        // }

        return ans;       
    }
};

 

Go

var n  int
var m  int
var dp [][][]int

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func getMax(row, col1, col2 int) int {
	maxNum := -1

	for i := max(0, col1-1); i <= min(m-1, col1+1); i++ {
		for j := max(0, col2-1); j <= min(m-1, col2+1); j++ {
			maxNum = max(maxNum, dp[row-1][i][j])
		}
	}
	return maxNum
}

func cherryPickup(grid [][]int) int {
	n = len(grid)
	m = len(grid[0])
	dp = make([][][]int, n)
	for i := range dp {
		dp[i] = make([][]int, m)
		for j := range dp[i] {
			dp[i][j] = make([]int, m)
			for k := range dp[i][j] {
				dp[i][j][k] = -1
			}
		}
	}

	dp[0][0][m-1] = grid[0][0] + grid[0][m-1]

	for i := 1; i < n; i++ {
		for j := 0; j < m; j++ {
			for k := 0; k < m; k++ {
				prev := getMax(i, j, k)
				if prev == -1 {
					continue
				}
				dp[i][j][k] = prev + grid[i][j] + grid[i][k]
				if j == k {
					dp[i][j][k] -= grid[i][j]
				}
			}
		}
	}

	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < m; j++ {
			ans = max(ans, dp[n-1][i][j])
		}
	}

	return ans
}