1463. Cherry Pickup II - Explanation

1. Recursion

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

        def dfs(r, c1, c2):
            if c1 < 0 or c2 < 0 or c1 >= COLS or c2 >= COLS or c1 > c2:
                return 0
            if r == ROWS - 1:
                return grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)

            res = 0
            for c1_d in [-1, 0, 1]:
                for c2_d in [-1, 0, 1]:
                    res = max(res, dfs(r + 1, c1 + c1_d, c2 + c2_d))

            return res + grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)

        return dfs(0, 0, COLS - 1)

Time & Space Complexity

Time complexity: $O(m * 9 ^ n)$
Space complexity: $O(n)$ for recursion stack.

Where $n$ is the number of rows and $m$ is the number of columns in the grid.

2. Dynamic Programming (Top-Down)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        cache = {}

        def dfs(r, c1, c2):
            if (r, c1, c2) in cache:
                return cache[(r, c1, c2)]
            if c1 == c2 or min(c1, c2) < 0 or max(c1, c2) >= COLS:
                return 0
            if r == ROWS - 1:
                return grid[r][c1] + grid[r][c2]

            res = 0
            for c1_d in [-1, 0, 1]:
                for c2_d in [-1, 0, 1]:
                    res = max(res, dfs(r + 1, c1 + c1_d, c2 + c2_d))

            cache[(r, c1, c2)] = res + grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)
            return cache[(r, c1, c2)]

        return dfs(0, 0, COLS - 1)

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity: $O(n * m ^ 2)$

Where $n$ is the number of rows and $m$ is the number of columns in the grid.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dp = [[[0] * COLS for _ in range(COLS)] for _ in range(ROWS)]

        for r in range(ROWS - 1, -1, -1):
            for c1 in range(COLS):
                for c2 in range(COLS):
                    res = grid[r][c1]
                    if c1 != c2:
                        res += grid[r][c2]

                    if r != ROWS - 1:
                        max_cherries = 0
                        for d1 in [-1, 0, 1]:
                            for d2 in [-1, 0, 1]:
                                nc1, nc2 = c1 + d1, c2 + d2
                                if 0 <= nc1 < COLS and 0 <= nc2 < COLS:
                                    max_cherries = max(max_cherries, dp[r + 1][nc1][nc2])
                        res += max_cherries

                    dp[r][c1][c2] = res

        return dp[0][0][COLS - 1]

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity: $O(n * m ^ 2)$

Where $n$ is the number of rows and $m$ is the number of columns in the grid.

4. Dynamic Programming (Space Optimized)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dp = [[0] * COLS for _ in range(COLS)]

        for r in reversed(range(ROWS)):
            cur_dp = [[0] * COLS for _ in range(COLS)]
            for c1 in range(COLS):
                for c2 in range(c1, COLS):
                    max_cherries = 0
                    cherries = grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)
                    for d1 in [-1, 0, 1]:
                        for d2 in [-1, 0, 1]:
                            nc1, nc2 = c1 + d1, c2 + d2
                            if 0 <= nc1 < COLS and 0 <= nc2 < COLS:
                                max_cherries = max(max_cherries, cherries + dp[nc1][nc2])
                    cur_dp[c1][c2] = max_cherries
            dp = cur_dp

        return dp[0][COLS - 1]

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity: $O(m ^ 2)$

Where $n$ is the number of rows and $m$ is the number of columns in the grid.