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

The idea here is to use dynamic programming with 3 states: dp[j][i1][i2], where j is the number of row and, i1 is the number of column for the first robot and i2 is the number of column for the second robot. I also added dummy columns filled with big negative numbers to handle with border cases.

First, we need to fill dp[0][1][M] value of our table, which corresponds to column 0 for the first robot and column M-1 for the second robot. Then we just go through the table and check all possible 3 x 3 = 9 cases for previous state of our robots, find maximum and update. We also need to deal with case, when they are at the same cell, which can be done with (grid[j][i1-1] + grid[j][i2-1])//(1 + (i1 == i2)) code. In the end we need to return maximum over possile M*M values in the last row, that is for dp[-1]

Complexity

We have O(9*M*M*N) time complexity, where M is number of columns and N is number of rows, because we potentially need to check upto 9 candidates. Time complexity is O(M*M*N) to keep dp table.

class Solution:
    def cherryPickup(self, grid):
        M, N = len(grid[0]), len(grid)

        dp = [[[-10**9] * (M+2) for _ in range(M+2)] for _ in range(N)]
        dp[0][1][M] = grid[0][0] + grid[0][M-1]
        for j in range(1, N):
            for i1, i2 in product(range(1, M+1), range(1, M+1)):
                cand_prev = []
                for shift1, shift2 in product([-1,0,1], [-1,0,1]):
                    cand_prev.append(dp[j-1][i1 + shift1][i2 + shift2])
                dp[j][i1][i2] = (grid[j][i1-1] + grid[j][i2-1])//(1 + (i1 == i2)) + max(cand_prev)

        return max(list(map(max, *dp[-1])))

If you like the solution, you can upvote it on leetcode discussion section: Problem 1463