Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The best path to a cell depends on how much robber-neutralization capacity is available. Keep three versions of each cell's answer, allowing at most zero, one, or two neutralizations. Negative rewards make it essential to distinguish unreachable states from a legitimate total of zero.

Approach

Let dp[i][j][k] be the best amount on reaching (i, j) using at most k neutralizations. Initialize states to negative infinity. At the starting cell, take its value unless it is negative and k > 0, in which case neutralizing it yields zero.

For every other cell, consider arriving from above or the left. Normally add the current value to the predecessor with the same budget. If the cell is negative and k > 0, also consider taking the predecessor's value with budget k - 1, neutralizing the current loss. Store the largest candidate.

Return the destination state with budget two. The budget is an upper bound, not an exact usage count, so solutions that need fewer neutralizations are included automatically.

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        n = len(coins)
        m = len(coins[0])
        dp = [[[-inf] * 3 for _ in range(m)] for _ in range(n)]

        for i in range(n):
            for j in range(m):
                for k in range(3):
                    val = coins[i][j]
                    if i == 0 and j == 0:
                        if val < 0 and k > 0:
                            dp[i][j][k] = 0
                        else:
                            dp[i][j][k] = val
                        continue
                    res = -inf
                    if i > 0:
                        res = max(res, val + dp[i - 1][j][k])
                        if val < 0 and k:
                            res = max(res, dp[i - 1][j][k - 1])
                    if j > 0:
                        res = max(res, val + dp[i][j - 1][k])
                        if val < 0 and k:
                            res = max(res, dp[i][j - 1][k - 1])
                    dp[i][j][k] = res

        return dp[-1][-1][2]

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c). Auxiliary space: O(r * c) because the neutralization dimension has constant size 3.