Cherry Pickup LeetCode solution in Python

1
# Runtime: 360 ms (Top 100.00%) | Memory: 14 MB (Top 98.73%)
2
class Solution:
3
    def cherryPickup(self, grid):
4
        n = len(grid)
5
        dp = [[-1] * (n + 1) for _ in range(n + 1)]
6
        dp[1][1] = grid[0][0]
7
        for m in range(1, (n << 1) - 1):
8
            for i in range(min(m, n - 1), max(-1, m - n), -1):
9
                for p in range(i, max(-1, m - n), -1):
10
                    j, q = m - i, m - p
11
                    if grid[i][j] == -1 or grid[p][q] == -1:
12
                        dp[i + 1][p + 1] = -1
13
                    else:
14
                        dp[i + 1][p + 1] = max(
15
                            dp[i + 1][p + 1], dp[i][p + 1], dp[i + 1][p], dp[i][p]
16
                        )
17
                        if dp[i + 1][p + 1] != -1:
18
                            dp[i + 1][p + 1] += grid[i][j] + (
19
                                grid[p][q] if i != p else 0
20
                            )
21
        return max(0, dp[-1][-1])