You are given an r rows and c cols matrix grid representing a field of chocolates where grid[i][j] represents the number of chocolates that you can collect from the (i, j) cell.
You have two robots that can collect chocolates for you:
Robot #1 is located at the top-left corner (0, 0), and
Robot #2 is located at the top-right corner (0, cols - 1).
Return the maximum number of chocolates collection using both robots by following the rules below:
From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
When any robot passes through a cell, It picks up all chocolates, and the cell becomes an empty cell.
When both robots stay in the same cell, only one takes the chocolates.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in grid.
Example:
Input:
r = 3, c = 4
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output:
24
Explanation:
Path of robot #1 and #2 are described in color green and blue respectively. Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12. Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12. Total of cherries: 12 + 12 = 24.
Your Task:
You don't need to read input or print anything. Your task is to complete the function Solve() which takes r rows, c columns, and a matrix grid and returns the maximum number of chocolates that can be collected by two robots.
Expected Time Complexity: O(r * c * c)
Expected Space Complexity: O(c * c * c)
Constraint:
2 <= r < = 70
0 <= grid[i][j] <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def solve(self, n, m, grid):

        # Code here

Solutions:
import sys

class Solution:

	def solve(self, n, m, grid):
		dp = [[[-1 for j in range(m)] for i in range(m)] for k in range(n)]
		return self.maxChocoUtil(0, 0, m - 1, n, m, grid, dp)

	def maxChocoUtil(self, i, j1, j2, n, m, grid, dp):
		if j1 < 0 or j1 >= m or j2 < 0 or (j2 >= m):
			return int(-1000000000.0)
		if i == n - 1:
			if j1 == j2:
				return grid[i][j1]
			else:
				return grid[i][j1] + grid[i][j2]
		if dp[i][j1][j2] != -1:
			return dp[i][j1][j2]
		maxi = -sys.maxsize
		for di in range(-1, 2):
			for dj in range(-1, 2):
				if j1 == j2:
					ans = grid[i][j1] + self.maxChocoUtil(i + 1, j1 + di, j2 + dj, n, m, grid, dp)
				else:
					ans = grid[i][j1] + grid[i][j2] + self.maxChocoUtil(i + 1, j1 + di, j2 + dj, n, m, grid, dp)
				maxi = max(maxi, ans)
		dp[i][j1][j2] = maxi
		return maxi


class Solution:

	def solve(self, n, m, grid):
		dp = {}

		def recursion(row, c1, c2):
			if c1 < 0 or c1 >= m or c2 < 0 or (c2 >= m):
				return -10 ** 9
			if row == n - 1:
				if c1 == c2:
					return grid[row][c1]
				return grid[row][c1] + grid[row][c2]
			if (row, c1, c2) in dp:
				return dp[row, c1, c2]
			maxi = float('-inf')
			for dir1 in range(-1, 2):
				currentAns = float('-inf')
				for dir2 in range(-1, 2):
					if c1 == c2:
						currentAns = max(currentAns, grid[row][c1] + recursion(row + 1, c1 + dir1, c2 + dir2))
					else:
						currentAns = max(currentAns, grid[row][c2] + grid[row][c1] + recursion(row + 1, c1 + dir1, c2 + dir2))
				maxi = max(maxi, currentAns)
			dp[row, c1, c2] = maxi
			return maxi
		return recursion(0, 0, m - 1)


from math import inf

class Solution:

	def solve(self, n, m, grid):
		dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]
		return self.helper(0, 0, m - 1, grid, dp)

	def helper(self, r, c1, c2, grid, dp):
		row_len = len(grid)
		col_len = len(grid[0])
		if c1 < 0 or c1 >= col_len or c2 < 0 or (c2 >= col_len):
			return -inf
		if r == row_len - 1:
			if c1 == c2:
				return grid[r][c1]
			return grid[r][c1] + grid[r][c2]
		if dp[r][c1][c2] != -1:
			return dp[r][c1][c2]
		if c1 == c2:
			choco_count = grid[r][c1]
		else:
			choco_count = grid[r][c1] + grid[r][c2]
		col_dirs = [-1, 0, 1]
		maxi = 0
		for i in range(3):
			for j in range(3):
				pickup = self.helper(r + 1, c1 + col_dirs[i], c2 + col_dirs[j], grid, dp)
				maxi = max(maxi, choco_count + pickup)
		dp[r][c1][c2] = maxi
		return dp[r][c1][c2]


class Solution:

	def solve(self, n, m, A):
		dp = [[0] * m for _ in range(m)]
		dp[0][m - 1] = A[0][0] + A[0][-1]
		for i in range(1, n):
			dpn = [[0] * m for _ in range(m)]
			for j in range(m):
				for k in range(m):
					if j > i or m - k - 1 > i:
						continue
					for dj in [-1, 0, 1]:
						for dk in [-1, 0, 1]:
							if 0 <= j + dj < m and 0 <= k + dk < m:
								dpn[j][k] = max(dpn[j][k], dp[j + dj][k + dk])
					dpn[j][k] += A[i][j] + A[i][k] - (0 if j != k else A[i][j])
			dp = dpn
		return max((x for r in dp for x in r))


class Solution:

	def solve(self, n, m, grid):
		dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]

		def helper(i, j1, j2):
			if j1 < 0 or j1 >= m or j2 < 0 or (j2 >= m):
				return -1000000000.0
			if i == n - 1:
				if j1 == j2:
					return grid[i][j1]
				return grid[i][j1] + grid[i][j2]
			if dp[i][j1][j2] != -1:
				return dp[i][j1][j2]
			maxi = 0
			for dj1 in range(-1, 2):
				for dj2 in range(-1, 2):
					if j1 == j2:
						value = grid[i][j1]
					else:
						value = grid[i][j1] + grid[i][j2]
					value += helper(i + 1, j1 + dj1, j2 + dj2)
					maxi = max(maxi, value)
			dp[i][j1][j2] = maxi
			return maxi
		return helper(0, 0, m - 1)


class Solution:

	def solve(self, n, m, grid):
		dp = [[[-1 for j in range(m)] for i in range(m)] for k in range(n)]
		n = len(grid)
		m = len(grid[0])
		return self.func(0, 0, m - 1, n, m, grid, dp)

	def func(self, i, j1, j2, n, m, grid, dp):
		if j1 < 0 or j1 >= m or j2 < 0 or (j2 >= m):
			return float('-inf')
		if i == n - 1:
			if j1 == j2:
				return grid[i][j1]
			else:
				return grid[i][j1] + grid[i][j2]
		if dp[i][j1][j2] != -1:
			return dp[i][j1][j2]
		maxi = 0
		for d1 in range(-1, 2):
			for d2 in range(-1, 2):
				rb = 0
				if j1 == j2:
					rb = grid[i][j1] + self.func(i + 1, j1 + d1, j2 + d2, n, m, grid, dp)
				else:
					rb = grid[i][j1] + grid[i][j2] + self.func(i + 1, j1 + d1, j2 + d2, n, m, grid, dp)
				maxi = max(maxi, rb)
		dp[i][j1][j2] = maxi
		return maxi


class Solution:

	def helper(self, n, m, grid, dp, i, j1, j2):
		if i < 0 or j1 < 0 or j2 < 0 or (i >= n) or (j1 >= m) or (j2 >= m):
			return float('-inf')
		if i == n - 1:
			if j1 == j2:
				return grid[i][j1]
			else:
				return grid[i][j1] + grid[i][j2]
		if dp[i][j1][j2] != -1:
			return dp[i][j1][j2]
		maxi = float('-inf')
		for r1 in range(-1, 2):
			for r2 in range(-1, 2):
				ans = 0
				if j1 != j2:
					ans = grid[i][j1] + grid[i][j2] + self.helper(n, m, grid, dp, i + 1, j1 + r1, j2 + r2)
				else:
					ans = grid[i][j1] + self.helper(n, m, grid, dp, i + 1, j1 + r1, j2 + r2)
				maxi = max(ans, maxi)
		dp[i][j1][j2] = maxi
		return maxi

	def solve(self, n, m, grid):
		n = len(grid)
		m = len(grid[0])
		dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]
		return self.helper(n, m, grid, dp, 0, 0, m - 1)


class Solution:

	def dfs(self, ind, j1, j2, grid, N, M, dp):
		if ind >= N:
			return 0
		if dp[ind][j1][j2] != -1:
			return dp[ind][j1][j2]
		ans = 0
		for i in [j1 - 1, j1, j1 + 1]:
			for j in [j2 - 1, j2, j2 + 1]:
				if i < M and i >= 0 and (j < M) and (j >= 0):
					if i == j:
						ans = max(ans, grid[ind][i] + self.dfs(ind + 1, i, j, grid, N, M, dp))
					else:
						ans = max(ans, grid[ind][i] + grid[ind][j] + self.dfs(ind + 1, i, j, grid, N, M, dp))
		dp[ind][j1][j2] = ans
		return ans

	def solve(self, n, m, grid):
		dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]
		if m - 1 == 0:
			return grid[0][0] + self.dfs(0, 0, m - 1, grid, n, m, dp)
		return grid[0][0] + grid[0][-1] + self.dfs(1, 0, m - 1, grid, n, m, dp)


class Solution:

	def solve(self, n, m, grid):
		dp = [[[-1] * m for i in range(m)] for j in range(n)]

		def choc(i, j1, j2):
			if j1 < 0 or j1 >= m or j2 < 0 or (j2 >= m):
				return -10 ** 8
			if i == n - 1:
				if j1 == j2:
					return grid[i][j1]
				else:
					return grid[i][j1] + grid[i][j2]
			if dp[i][j1][j2] != -1:
				return dp[i][j1][j2]
			maxi = -10 ** 8
			for d1 in range(-1, 2):
				for d2 in range(-1, 2):
					if j1 == j2:
						val = grid[i][j1]
					else:
						val = grid[i][j1] + grid[i][j2]
					val += choc(i + 1, j1 + d1, j2 + d2)
					maxi = max(maxi, val)
			dp[i][j1][j2] = maxi
			return dp[i][j1][j2]
		return choc(0, 0, m - 1)


class Solution:

	def solve(self, n, m, grid):
		dictio = {(1, -1), (1, 0), (1, 1)}
		m = len(grid)
		n = len(grid[0])
		dp = {}

		def f(i, j, r, c):
			if (i, j, r, c) in dp:
				return dp[i, j, r, c]
			if i == m - 1:
				if j == c:
					return grid[-1][j]
				else:
					return grid[-1][j] + grid[-1][c]
			if j == c:
				cur = grid[i][j]
			else:
				cur = grid[i][j] + grid[r][c]
			maxi = 0
			for (di, dj) in dictio:
				(n_i, n_j) = (i + di, j + dj)
				if n_i >= 0 and n_j >= 0 and (n_i < m) and (n_j < n):
					for (di, dj) in dictio:
						(nn_i, nn_j) = (r + di, c + dj)
						if nn_i >= 0 and nn_j >= 0 and (nn_i < m) and (nn_j < n):
							maxi = max(maxi, cur + f(n_i, n_j, nn_i, nn_j))
			dp[i, j, r, c] = maxi
			return maxi
		return f(0, 0, 0, n - 1)


from functools import lru_cache

class Solution:

	def solve(self, n, m, grid):
		(R, C) = (n, m)

		@lru_cache(None)
		def dfs(r=0, c1=0, c2=C - 1):
			if r == R:
				return 0
			cherr = grid[r][c1] + (0 if c1 == c2 else grid[r][c2])
			ans = 0
			for nc1 in range(c1 - 1, c1 + 2):
				for nc2 in range(c2 - 1, c2 + 2):
					if 0 <= nc1 < C and 0 <= nc2 < C:
						ans = max(ans, dfs(r + 1, nc1, nc2))
			return ans + cherr
		return dfs()


class Solution:

	def solve(self, n, m, grid):
		memo = {}

		def dp(i, j1, j2):
			if j1 >= m or j1 < 0 or j2 >= m or (j2 < 0):
				return 0
			k = (i, j1, j2)
			if k in memo:
				return memo[k]
			ans = grid[i][j1]
			if j2 != j1:
				ans += grid[i][j2]
			if i == n - 1:
				return ans
			bestNext = 0
			for dj1 in range(-1, 2):
				for dj2 in range(-1, 2):
					bestNext = max(bestNext, dp(i + 1, j1 + dj1, j2 + dj2))
			ans += bestNext
			memo[k] = ans
			return ans
		return dp(0, 0, m - 1)