Maximum Amount of Money Robot Can Earn

Problem

We are given an m x n grid where each cell contains either:

• a non-negative value, meaning the robot earns coins
• a negative value, meaning a robber steals coins

The robot starts at (0, 0) and wants to reach (m - 1, n - 1), moving only right or down.

There is one twist: the robot can neutralize robbers in at most 2 cells, which means those negative cells contribute 0 instead of reducing the answer.

The goal is to return the maximum total profit possible.

One important detail: the final total is allowed to be negative.

First Thought

This is clearly a grid DP problem because:

• we move only right or down
• every state depends on top and left
• we want the best possible total by the time we reach a cell

The only extra complication is the neutralization ability.

If we ignore that ability, a normal 2D DP would work. But once we can neutralize up to 2 robbers, the answer at a cell depends not just on position, but also on how many neutralizations we have already used.

That is why we need a 3D DP.

DP State

Let:

dp[i][j][k] = maximum coins we can have when reaching cell (i, j) using exactly k neutralizations

Here:

• i = row
• j = column
• k = 0, 1, or 2

Using exactly k neutralizations makes transitions very clean.

At the end, the answer is:

max(dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2])

because we are allowed to use at most 2, not necessarily all 2.

Why Exactly k Works Better

There are two ways to handle the current cell:

1. Do not neutralize this cell

Then the number of used neutralizations stays the same.

So we can come from:

• dp[i - 1][j][k]
• dp[i][j - 1][k]

and add coins[i][j].

2. Neutralize this cell

This only makes sense if coins[i][j] < 0.

If we neutralize here, then one extra neutralization is used at this cell, so we must come from:

• dp[i - 1][j][k - 1]
• dp[i][j - 1][k - 1]

and add 0 instead of the negative value.

That gives us a very natural transition.

Transition

For every cell (i, j) and every k in [0, 2]:

Case 1: do not neutralize current cell

Take the best previous value from top or left using the same k, then add coins[i][j].

Case 2: neutralize current cell

If the current cell is negative and k > 0, take the best previous value from top or left using k - 1, and carry it forward unchanged.

In code, that becomes:

int bestPrev = NEG;

if (i > 0) bestPrev = Math.max(bestPrev, dp[i - 1][j][k]);
if (j > 0) bestPrev = Math.max(bestPrev, dp[i][j - 1][k]);

if (bestPrev != NEG) {
  dp[i][j][k] = Math.max(dp[i][j][k], bestPrev + coins[i][j]);
}

if (coins[i][j] < 0 && k > 0) {
  int bestPrevNeutral = NEG;

  if (i > 0) bestPrevNeutral = Math.max(bestPrevNeutral, dp[i - 1][j][k - 1]);
  if (j > 0) bestPrevNeutral = Math.max(bestPrevNeutral, dp[i][j - 1][k - 1]);

  if (bestPrevNeutral != NEG) {
    dp[i][j][k] = Math.max(dp[i][j][k], bestPrevNeutral);
  }
}

Base Case

The start cell needs special handling.

If coins[0][0] >= 0, then:

• dp[0][0][0] = coins[0][0]

If coins[0][0] < 0, then we have two choices:

• do not neutralize it: dp[0][0][0] = coins[0][0]
• neutralize it: dp[0][0][1] = 0

That is an easy detail to miss, and it matters.

Full Java Solution

class Solution {
  public int maximumAmount(int[][] coins) {
    int m = coins.length;
    int n = coins[0].length;

    // dp[i][j][k] = max coins at (i, j) using exactly k neutralizations
    int[][][] dp = new int[m][n][3];
    int NEG = Integer.MIN_VALUE / 4;

    // initialize all as unreachable
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < 3; k++) {
          dp[i][j][k] = NEG;
        }
      }
    }

    // base case: start cell
    if (coins[0][0] >= 0) {
      dp[0][0][0] = coins[0][0];
    } else {
      // do not neutralize start cell
      dp[0][0][0] = coins[0][0];
      // neutralize start cell
      dp[0][0][1] = 0;
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // skip start, already initialized
        if (i == 0 && j == 0) continue;

        for (int k = 0; k < 3; k++) {
          int bestPrev = NEG;

          if (i > 0) bestPrev = Math.max(bestPrev, dp[i - 1][j][k]);
          if (j > 0) bestPrev = Math.max(bestPrev, dp[i][j - 1][k]);

          if (bestPrev != NEG) {
            // do not neutralize this cell
            dp[i][j][k] = Math.max(dp[i][j][k], bestPrev + coins[i][j]);
          }

          // neutralize this cell if it is negative and we have used one more neutralization
          if (coins[i][j] < 0 && k > 0) {
            int bestPrevNeutral = NEG;
            if (i > 0) bestPrevNeutral = Math.max(bestPrevNeutral, dp[i - 1][j][k - 1]);
            if (j > 0) bestPrevNeutral = Math.max(bestPrevNeutral, dp[i][j - 1][k - 1]);

            if (bestPrevNeutral != NEG) {
              dp[i][j][k] = Math.max(dp[i][j][k], bestPrevNeutral);
            }
          }
        }
      }
    }

    return Math.max(dp[m - 1][n - 1][0],
        Math.max(dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]));
  }
}

Walkthrough

Take:

coins = [
  [0,  1, -1],
  [1, -2,  3],
  [2, -3,  4]
]

One optimal route is:

1. Start at (0, 0) with 0
2. Move right to (0, 1) and gain 1
3. Move down to (1, 1), which is -2, and neutralize it
4. Move right to (1, 2) and gain 3
5. Move down to (2, 2) and gain 4

Total = 0 + 1 + 0 + 3 + 4 = 8

The DP naturally tries all right/down paths and all valid ways to spend 0, 1, or 2 neutralizations, then keeps only the best.

Complexity Analysis

Time Complexity: O(m * n * 3) which is simply O(m * n)

• for every cell, we process 3 neutralization states
• each transition checks only top and left

Space Complexity: O(m * n * 3) which is O(m * n)

Common Mistakes

1. Using only 2D DP

That loses information.

Reaching the same cell with:

• 0 neutralizations used
• 1 neutralization used
• 2 neutralizations used

are all different states.

2. Forgetting the start cell can also be neutralized

If coins[0][0] is negative, we may want to spend one neutralization immediately.

3. Using a very small negative sentinel

If you use Integer.MIN_VALUE directly and then do:

bestPrev + coins[i][j]

you risk overflow.

Using something like Integer.MIN_VALUE / 4 is safer.

4. Mixing up "exactly 2" with "at most 2"

We track exactly k used inside DP, but the final answer takes the max over k = 0, 1, 2.

Why I Like This Solution

This problem looks slightly tricky at first because of the robber neutralization rule, but once you add that rule into the DP state, everything becomes systematic.

The nice part is that the transition stays local:

• from top
• from left
• same k if we do not neutralize
• k - 1 if we do neutralize

That is exactly the kind of pattern grid DP is great at.

Related Problems

• Minimum Path Sum — Medium
• Dungeon Game — Hard
• Cherry Pickup II — Hard