[leetcode] 1463. Cherry Pickup II

문제 : https://leetcode.com/problems/cherry-pickup-ii/

---

rows x cols 체리 필드(grid)가 주어지고 각 요소값은 체리 수를 의미한다.

로봇1은 왼쪽 상단 (0,0)에서 출발하고 로봇2는 오른쪽 상단 (0, cols-1)에서 출발한다.

셀 (i,j)에서 로봇은 (i+1, j-1), (i+1, j), (i+1, j+1) 3가지 중에 한 곳으로 이동할 수 있다.

두 로봇이 동일한 셀에 있을 때 한 로봇만 체리를 가져갈 수 있다.

로봇들이 이동할 때, 수집할 수 있는 체리의 최대 수를 구해라.

---

DP로 풀 수 있다.

 

dp[row][col1][col2] = 로봇1은 (row, col1), 로봇2는 (row, col1)에 있을 때 수집가능한 체리수의 최대값.

dp[row][col1][col2] = grid[row][col1] + grid[row][col2]

+ max(dp[row-1][col1-1][col2-1],  dp[row-1][col1-1][col2], dp[row-1][col1-1][col2+1],

           dp[row][col1-1][col2-1],  dp[row][col1-1][col2], dp[row][col1-1][col2+1],

           dp[row+1][col1-1][col2-1],  dp[row+1][col1-1][col2], dp[row+1][col1-1][col2+1])                   

 

 

공간/시간 복잡도는 O(NM^2). N = rows, M = cols

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1463.%20Cherry%20Pickup%20II.cpp