741. Cherry Pickup - Explanation

Description

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

0 means the cell is empty, so you can pass through,
1 means the cell contains a cherry that you can pick up and pass through, or
-1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Example 1:

Input: grid = [
    [0,1,-1],
    [1,0,-1],
    [1,1,1]
]

Output: 5

Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

Example 2:

Input: grid = [
    [1,1,-1],
    [1,-1,1],
    [-1,1,1]
]

Output: 0

Constraints:

1 <= grid.length == grid[i].length <= 50
grid[i][j] is -1, 0, or 1.
grid[0][0] != -1
grid[n - 1][n - 1] != -1

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        def dfs(r1, c1, r2, c2):
            if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
                return -1000

            if r1 == n - 1 and r2 == n - 1 and c1 == n - 1 and c2 == n - 1:
                return grid[r1][c1]

            res = dfs(r1 + 1, c1, r2 + 1, c2)
            res = max(res, dfs(r1 + 1, c1, r2, c2 + 1))
            res = max(res, dfs(r1, c1 + 1, r2 + 1, c2))
            res = max(res, dfs(r1, c1 + 1, r2, c2 + 1))
            res += grid[r1][c1] + grid[r2][c2]
            res -= (grid[r1][c1] if (r1 == r2 and c1 == c2) else 0)
            return res

        return max(0, dfs(0, 0, 0, 0))

Time & Space Complexity

Time complexity: $O(16 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[[[float("-inf")] * n for _ in range(n)] for _ in range(n)] for _ in range(n)]

        def dfs(r1, c1, r2, c2):
            if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
                return -1000

            if r1 == n - 1 and r2 == n - 1 and c1 == n - 1 and c2 == n - 1:
                return grid[r1][c1]

            if dp[r1][c1][r2][c2] != float("-inf"):
                return dp[r1][c1][r2][c2]

            res = dfs(r1 + 1, c1, r2 + 1, c2)
            res = max(res, dfs(r1 + 1, c1, r2, c2 + 1))
            res = max(res, dfs(r1, c1 + 1, r2 + 1, c2))
            res = max(res, dfs(r1, c1 + 1, r2, c2 + 1))
            res += grid[r1][c1] + grid[r2][c2]
            if r1 == r2 and c1 == c2:
                res -= grid[r1][c1]

            dp[r1][c1][r2][c2] = res
            return res

        return max(0, dfs(0, 0, 0, 0))

Time & Space Complexity

Time complexity: $O(n ^ 4)$
Space complexity: $O(n ^ 4)$

3. Dynamic Programming (Top-Down) Optimized

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[[float("-inf")] * n for _ in range(n)] for _ in range(n)]

        def dfs(r1, c1, r2):
            c2 = r1 + c1 - r2
            if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
                return -1000

            if r1 == n - 1 and c1 == n - 1:
                return grid[r1][c1]

            if dp[r1][c1][r2] != float("-inf"):
                return dp[r1][c1][r2]

            res = dfs(r1 + 1, c1, r2 + 1)
            res = max(res, dfs(r1 + 1, c1, r2))
            res = max(res, dfs(r1, c1 + 1, r2 + 1))
            res = max(res, dfs(r1, c1 + 1, r2))
            res += grid[r1][c1]
            if (r1, c1) != (r2, c2):
                res += grid[r2][c2]

            dp[r1][c1][r2] = res
            return res

        return max(0, dfs(0, 0, 0))

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 3)$

4. Dynamic Programming (Bottom-Up)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[[float("-inf")] * n for _ in range(n)] for _ in range(n)]

        for r1 in reversed(range(n)):
            for c1 in reversed(range(n)):
                for r2 in reversed(range(n)):
                    c2 = r1 + c1 - r2
                    if c2 < 0 or c2 >= n:
                        continue
                    if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                        continue

                    if r1 == n - 1 and c1 == n - 1:
                        dp[r1][c1][r2] = grid[r1][c1]
                    else:
                        res = max(
                            dp[r1 + 1][c1][r2 + 1] if r1 + 1 < n and r2 + 1 < n else -1000,
                            dp[r1 + 1][c1][r2] if r1 + 1 < n else -1000,
                            dp[r1][c1 + 1][r2 + 1] if c1 + 1 < n and r2 + 1 < n else -1000,
                            dp[r1][c1 + 1][r2] if c1 + 1 < n else -1000
                        )
                        if res == -1000:
                            continue
                        res += grid[r1][c1]
                        if (r1, c1) != (r2, c2):
                            res += grid[r2][c2]
                        dp[r1][c1][r2] = res

        return max(0, dp[0][0][0])

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 3)$

5. Dynamic Programming (Space Optimized)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        prev = [[float("-inf")] * n for _ in range(n)]
        prev[0][0] = grid[0][0]

        for k in range(1, 2 * n - 1):
            dp = [[float("-inf")] * n for _ in range(n)]
            for r1 in range(max(0, k - (n - 1)), min(n, k + 1)):
                c1 = k - r1
                if c1 >= n or grid[r1][c1] == -1:
                    continue
                for r2 in range(max(0, k - (n - 1)), min(n, k + 1)):
                    c2 = k - r2
                    if c2 >= n or grid[r2][c2] == -1:
                        continue
                    val = prev[r1][r2]
                    if r1 > 0: val = max(val, prev[r1 - 1][r2])
                    if r2 > 0: val = max(val, prev[r1][r2 - 1])
                    if r1 > 0 and r2 > 0: val = max(val, prev[r1 - 1][r2 - 1])
                    if val < 0: continue
                    val += grid[r1][c1]
                    if r1 != r2: val += grid[r2][c2]
                    dp[r1][r2] = val
            prev = dp

        return max(0, prev[n - 1][n - 1])

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 2)$