# Maximum Amount of Money Robot Can Earn
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-amount-of-money-robot-can-earn)
Canonical: https://scaleengineer.com/dsa/problems/maximum-amount-of-money-robot-can-earn
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
You are given an `m x n` grid. A robot starts at the top-left corner of the grid `(0, 0)` and wants to reach the bottom-right corner `(m - 1, n - 1)`. The robot can move either right or down at any point in time.

The grid contains a value `coins[i][j]` in each cell:

* If `coins[i][j] >= 0`, the robot gains that many coins.
* If `coins[i][j] < 0`, the robot encounters a robber, and the robber steals the **absolute** value of `coins[i][j]` coins.

The robot has a special ability to **neutralize robbers** in at most **2 cells** on its path, preventing them from stealing coins in those cells.

**Note:** The robot's total coins can be negative.

Return the **maximum** profit the robot can gain on the route.

**Example 1:**

**Input:** coins = \[\[0,1,-1\],\[1,-2,3\],\[2,-3,4\]\]

**Output:** 8

**Explanation:**

An optimal path for maximum coins is:

1. Start at `(0, 0)` with `0` coins (total coins = `0`).
2. Move to `(0, 1)`, gaining `1` coin (total coins = `0 + 1 = 1`).
3. Move to `(1, 1)`, where there's a robber stealing `2` coins. The robot uses one neutralization here, avoiding the robbery (total coins = `1`).
4. Move to `(1, 2)`, gaining `3` coins (total coins = `1 + 3 = 4`).
5. Move to `(2, 2)`, gaining `4` coins (total coins = `4 + 4 = 8`).

**Example 2:**

**Input:** coins = \[\[10,10,10\],\[10,10,10\]\]

**Output:** 40

**Explanation:**

An optimal path for maximum coins is:

1. Start at `(0, 0)` with `10` coins (total coins = `10`).
2. Move to `(0, 1)`, gaining `10` coins (total coins = `10 + 10 = 20`).
3. Move to `(0, 2)`, gaining another `10` coins (total coins = `20 + 10 = 30`).
4. Move to `(1, 2)`, gaining the final `10` coins (total coins = `30 + 10 = 40`).

**Constraints:**

* `m == coins.length`
* `n == coins[i].length`
* `1 <= m, n <= 500`
* `-1000 <= coins[i][j] <= 1000`

# Approaches
## Dynamic Programming with 3D State
This problem can be solved using dynamic programming. Since the robot's decisions depend on its current position and the number of neutralizations used, we can define a state by `(row, column, neutralizations_used)`. A 3D DP table can store the optimal results for each state.
**Time:** O(m * n), as we iterate through each cell of the grid and perform a constant number of operations (for k=0, 1, 2). · **Space:** O(m * n), for the 3D DP table of size m x n x 3.
**Pros:** It's a standard and clear application of dynamic programming.; Guaranteed to find the optimal solution.; Efficient enough for the given problem constraints.
**Cons:** Uses O(m * n) space, which might be substantial for very large grids, although it fits within the memory limits for the given constraints.
### Explanation
We define a 3D DP array, `dp[i][j][k]`, which stores the maximum amount of money the robot can have when it reaches cell `(i, j)` having used exactly `k` neutralizations on its path. The third dimension `k` will have a size of 3, for 0, 1, or 2 neutralizations.

The state transition works as follows: to compute the value for `dp[i][j][k]`, we look at the maximum possible scores from the cells the robot could have come from, which are `(i-1, j)` (from top) and `(i, j-1)` (from left).

Let `max_prev(k)` be `max(dp[i-1][j][k], dp[i][j-1][k])`.

- If `coins[i][j] >= 0`: The robot collects the coins. The number of neutralizations used does not change. So, `dp[i][j][k] = max_prev(k) + coins[i][j]`.

- If `coins[i][j] < 0`: The robot encounters a robber and has two choices:
  1. **Don't neutralize:** The robot loses coins. The total coins would be `max_prev(k) + coins[i][j]`.
  2. **Neutralize:** This is possible only if `k > 0`. The robot uses one neutralization charge at `(i, j)`. The cost of this cell becomes 0. The state must have transitioned from a path that had used `k-1` neutralizations. So, the total coins would be `max_prev(k-1)`.

`dp[i][j][k]` is the maximum of these two options. After filling the entire `dp` table, the maximum profit at the destination `(m-1, n-1)` is the maximum value across all possible neutralization counts, i.e., `max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])`.

```java
class Solution {
    public long maxAmountOfMoney(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        long[][][] dp = new long[m][n][3];
        long UNREACHABLE = Long.MIN_VALUE / 2; // Use a very small number for unreachable states

        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] = UNREACHABLE;
                }
            }
        }

        // Base case: starting cell (0, 0)
        if (coins[0][0] >= 0) {
            dp[0][0][0] = coins[0][0];
        } else { // Robber at start
            dp[0][0][0] = coins[0][0]; // Don't neutralize
            dp[0][0][1] = 0;           // Neutralize
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                for (int k = 0; k < 3; k++) {
                    long maxPrevSameK = UNREACHABLE;
                    if (i > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i - 1][j][k]);
                    if (j > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i][j - 1][k]);

                    long maxPrevMinusOneK = UNREACHABLE;
                    if (k > 0) {
                        if (i > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i - 1][j][k - 1]);
                        if (j > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i][j - 1][k - 1]);
                    }

                    if (coins[i][j] >= 0) {
                        if (maxPrevSameK != UNREACHABLE) {
                            dp[i][j][k] = maxPrevSameK + coins[i][j];
                        }
                    } else { // Robber at (i, j)
                        long option1 = (maxPrevSameK != UNREACHABLE) ? maxPrevSameK + coins[i][j] : UNREACHABLE;
                        long option2 = (maxPrevMinusOneK != UNREACHABLE) ? maxPrevMinusOneK : UNREACHABLE;
                        
                        if (option1 != UNREACHABLE || option2 != UNREACHABLE) {
                            dp[i][j][k] = Math.max(option1, option2);
                        }
                    }
                }
            }
        }

        long result = UNREACHABLE;
        for (int k = 0; k < 3; k++) {
            result = Math.max(result, dp[m - 1][n - 1][k]);
        }
        
        return result;
    }
}
```
### Algorithm
- Create a 3D DP table `dp[i][j][k]` to store the maximum coins to reach cell `(i, j)` using exactly `k` neutralizations.
- Initialize the `dp` table with a very small number to represent unreachable states.
- Set the base case for the starting cell `(0, 0)`. If `coins[0][0]` is positive, `dp[0][0][0] = coins[0][0]`. If it's negative, `dp[0][0][0] = coins[0][0]` (no neutralization) and `dp[0][0][1] = 0` (one neutralization).
- Iterate through the grid from `(0, 0)` to `(m-1, n-1)`.
- For each cell `(i, j)` and for each neutralization count `k` (from 0 to 2), calculate `dp[i][j][k]` based on the values from the top cell `dp[i-1][j]` and the left cell `dp[i][j-1]`.
- If `coins[i][j]` is non-negative, the value is `max(from_top, from_left) + coins[i][j]` using the same `k`.
- If `coins[i][j]` is negative (a robber), there are two choices:
  1. Don't neutralize: `max(from_top, from_left)_k + coins[i][j]`.
  2. Neutralize (if `k > 0`): `max(from_top, from_left)_{k-1}`.
- The value `dp[i][j][k]` is the maximum of the valid choices.
- The final answer is the maximum value among `dp[m-1][n-1][0]`, `dp[m-1][n-1][1]`, and `dp[m-1][n-1][2]`.

## Space-Optimized Dynamic Programming
This approach optimizes the space complexity of the standard DP solution. By observing that the calculation for the current row only depends on the previous row, we can avoid storing the entire `m x n` grid. We only need to keep track of two rows at a time, significantly reducing memory usage.
**Time:** O(m * n), same as the previous approach. · **Space:** O(n), as we only need to store two rows of size n x 3.
**Pros:** Highly memory-efficient, making it suitable for problems with very large row counts.; Maintains the same optimal time complexity as the unoptimized version.
**Cons:** The implementation can be slightly more complex due to managing two arrays and handling the first row/column as special cases.
### Explanation
The `O(m * n)` space complexity of the previous approach can be optimized. When we compute the DP values for row `i`, we only need access to the values from row `i-1` and the values already computed in the current row `i`. This suggests that we don't need to store the entire DP table in memory.

We can use two arrays, say `prevDp` and `currDp`, each of size `n x 3`. `prevDp` will hold the DP values for the previous row (`i-1`), and `currDp` will be used to calculate the values for the current row (`i`).

The process is as follows:
1.  First, we compute the DP values for the entire first row (`i=0`) and store them in `prevDp`.
2.  Then, we iterate from `i = 1` to `m-1`. In each iteration, we compute `currDp` for row `i`.
3.  To calculate `currDp[j][k]`, we use `prevDp[j][k]` (value from the cell above) and `currDp[j-1][k]` (value from the cell to the left).
4.  After row `i` is fully computed in `currDp`, we no longer need the old `prevDp`. So, we set `prevDp = currDp` and prepare a new `currDp` for the next row.
5.  This process continues until we have computed the values for the last row.

The final result is the maximum value in the `prevDp` array for the last column, `n-1`.

```java
class Solution {
    public long maxAmountOfMoney(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        long UNREACHABLE = Long.MIN_VALUE / 2;

        long[][] prevDp = new long[n][3];

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 3; k++) {
                prevDp[j][k] = UNREACHABLE;
            }
        }

        // Initialize for the first row (i=0)
        if (coins[0][0] >= 0) {
            prevDp[0][0] = coins[0][0];
        } else {
            prevDp[0][0] = coins[0][0];
            prevDp[0][1] = 0;
        }

        for (int j = 1; j < n; j++) {
            for (int k = 0; k < 3; k++) {
                long fromLeftSameK = prevDp[j - 1][k];
                long fromLeftMinusOneK = (k > 0) ? prevDp[j - 1][k - 1] : UNREACHABLE;
                
                if (coins[0][j] >= 0) {
                    if (fromLeftSameK != UNREACHABLE) prevDp[j][k] = fromLeftSameK + coins[0][j];
                } else {
                    long opt1 = (fromLeftSameK != UNREACHABLE) ? fromLeftSameK + coins[0][j] : UNREACHABLE;
                    long opt2 = fromLeftMinusOneK;
                    if (opt1 != UNREACHABLE || opt2 != UNREACHABLE) prevDp[j][k] = Math.max(opt1, opt2);
                }
            }
        }

        // Iterate through the rest of the rows
        for (int i = 1; i < m; i++) {
            long[][] currDp = new long[n][3];
            for (int j = 0; j < n; j++) for (int k = 0; k < 3; k++) currDp[j][k] = UNREACHABLE;

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    long fromTopSameK = prevDp[j][k];
                    long fromLeftSameK = (j > 0) ? currDp[j - 1][k] : UNREACHABLE;
                    long maxPrevSameK = Math.max(fromTopSameK, fromLeftSameK);
                    if (fromTopSameK == UNREACHABLE) maxPrevSameK = fromLeftSameK;
                    if (fromLeftSameK == UNREACHABLE) maxPrevSameK = fromTopSameK;

                    long fromTopMinusOneK = (k > 0) ? prevDp[j][k - 1] : UNREACHABLE;
                    long fromLeftMinusOneK = (k > 0 && j > 0) ? currDp[j - 1][k - 1] : UNREACHABLE;
                    long maxPrevMinusOneK = Math.max(fromTopMinusOneK, fromLeftMinusOneK);
                    if (fromTopMinusOneK == UNREACHABLE) maxPrevMinusOneK = fromLeftMinusOneK;
                    if (fromLeftMinusOneK == UNREACHABLE) maxPrevMinusOneK = fromTopMinusOneK;

                    if (coins[i][j] >= 0) {
                        if (maxPrevSameK != UNREACHABLE) currDp[j][k] = maxPrevSameK + coins[i][j];
                    } else { // Robber
                        long opt1 = (maxPrevSameK != UNREACHABLE) ? maxPrevSameK + coins[i][j] : UNREACHABLE;
                        long opt2 = maxPrevMinusOneK;
                        if (opt1 != UNREACHABLE || opt2 != UNREACHABLE) currDp[j][k] = Math.max(opt1, opt2);
                    }
                }
            }
            prevDp = currDp;
        }

        long result = UNREACHABLE;
        for (int k = 0; k < 3; k++) {
            result = Math.max(result, prevDp[n - 1][k]);
        }
        return result;
    }
}
```
### Algorithm
- Observe that computing the DP values for row `i` only requires the values from row `i-1`.
- Use two 2D arrays, `prevDp` and `currDp`, both of size `n x 3`, to store DP values for the previous and current rows, respectively.
- Initialize `prevDp` by computing the results for the first row (`i=0`) of the grid.
- Iterate from the second row (`i=1`) to the last row (`m-1`).
- In each iteration `i`, compute `currDp` based on `prevDp` (for values from the top cell) and `currDp` itself (for values from the left cell).
- After computing the entire `currDp` for row `i`, swap the roles of the arrays: `prevDp` becomes `currDp` for the next iteration.
- The final answer is the maximum value in the last row of the `prevDp` table, i.e., `max(prevDp[n-1][0], prevDp[n-1][1], prevDp[n-1][2])`.

# Solutions
### Java

```java
class Solution {
private
  Integer[][][] f;
private
  int[][] coins;
private
  int m;
private
  int n;
public
  int maximumAmount(int[][] coins) {
    m = coins.length;
    n = coins[0].length;
    this.coins = coins;
    f = new Integer[m][n][3];
    return dfs(0, 0, 2);
  }
private
  int dfs(int i, int j, int k) {
    if (i >= m || j >= n) {
      return Integer.MIN_VALUE / 2;
    }
    if (f[i][j][k] != null) {
      return f[i][j][k];
    }
    if (i == m - 1 && j == n - 1) {
      return k > 0 ? Math.max(0, coins[i][j]) : coins[i][j];
    }
    int ans = coins[i][j] + Math.max(dfs(i + 1, j, k), dfs(i, j + 1, k));
    if (coins[i][j] < 0 && k > 0) {
      ans = Math.max(ans, Math.max(dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)));
    }
    return f[i][j][k] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumAmount(vector<vector<int>> &coins) {
    int m = coins.size(), n = coins[0].size();
    vector<vector<vector<int>>> f(m,
                                  vector<vector<int>>(n, vector<int>(3, -1)));
    auto dfs = [&](this auto &&dfs, int i, int j, int k) -> int {
      if (i >= m || j >= n) {
        return INT_MIN / 2;
      }
      if (f[i][j][k] != -1) {
        return f[i][j][k];
      }
      if (i == m - 1 && j == n - 1) {
        return k > 0 ? max(0, coins[i][j]) : coins[i][j];
      }
      int ans = coins[i][j] + max(dfs(i + 1, j, k), dfs(i, j + 1, k));
      if (coins[i][j] < 0 && k > 0) {
        ans = max({ans, dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)});
      }
      return f[i][j][k] = ans;
    };
    return dfs(0, 0, 2);
  }
};

```

### Python

```python
class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int: @ cache def dfs(i: int, j: int, k: int) -> int: if i >= m or j >= n: return - inf if i == m - 1 and j == n - 1: return max(coins[i][j], 0) if k else coins[i][j] ans = coins[i][j] + max(dfs(i + 1, j, k), dfs(i, j + 1, k)) if coins[i][j] < 0 and k: ans = max(ans, dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)) return ans m, n = len(coins), len(coins[0]) return dfs(0, 0, 2)

```