1463. Cherry Pickup II

[zeikar]

Problem link

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

Problem Summary

로봇이 첫 번째 행의 첫 번째 열과 마지막 열에 2개 있고 아래로 3 방향으로 내려가면서 최대로 체리를 얻을 수 있는 개수를 구하는 문제.

Solution

일단 간단한 DP 문제이긴 한데 궁금증이 하나 있다. 두 로봇이 같은 셀로 들어가는게 좋은 경우가 있을까?
결론은 없다. 만약 두 로봇이 같은 셀로 들어갔다고 해도 다음 경로를 정할 때는 다른 셀로 들어가야 할텐데 굳이 한 셀로 모이지 않더라도 각각 최대의 셀로 갈 수 있기 때문이다. (말로 하니 복잡한데 아무튼 중복으로 같은 셀로 들어가는 경우는 처리할 필요가 없다.)

구현은 TopDown DP이고 시간복잡도는 O(m*n^2) 이다. (m: 행, n: 열)

Source Code

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        @cache
        def pick(x, y1, y2):
            if x == rows:
                return 0

            res = 0
            n = [-1, 0, 1]

            for next1 in n:
                for next2 in n:
                    ny1 = y1 + next1
                    ny2 = y2 + next2
                    if ny1 < 0 or ny1 >= cols or ny2 < 0 or ny2 >= cols:
                        continue

                    if ny1 == ny2:
                        continue

                    res = max(res, pick(x + 1, ny1, ny2) +
                              grid[x][y1] + grid[x][y2])

            return res

        return pick(0, 0, cols - 1)