Cherry Pickup II

#Bottom up Approach Space optimised
'''
Both robots move down at same time (thus, at same row always)
Dp[i][j][k] = max cherries picked up with the initial position of two robots being (i, j) and (i, k)
Dp[i][j][k] = grid[j] + grid[k] + max(dp[i+1][a][b]) If j != k
            = grid[j] + max(dp[i+1][a][b]) ... J == k
            = 0 for i>=rows, j,k<0 j,k >= cols
Here |j-a| <= 1 and |k-b| <= 1
Time: O(m*n*n)
Space: O(n*n)
'''
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dp = [[0]*cols for _ in range(cols)]
        for i in range(rows-1, -1, -1):
            temp = [ele[:] for ele in dp]
            for j in range(cols):
                for k in range(j, cols):
                    m = 0
                    for a in range(-1, 2):
                        for b in range(-1, 2):
                            c1 = j + a
                            c2 = k + b
                            if 0<=c1<cols and 0<=c2<cols:
                                m = max(m, dp[c1][c2])
                    if j == k:
                        temp[j][k] = temp[k][j] = grid[i][j] + m
                    else:
                        temp[j][k] = temp[k][j] = grid[i][j] + grid[i][k] + m
            dp = temp
        return dp[0][cols-1]