489 ms Beats 54.37% || All Test Case Passed
IntuitionThe intuition behind the solution is to track the maximum coins the robot can collect while considering the two key factors: the robot's ability to neu
# Intuition
The intuition behind the solution is to **track the maximum coins** the robot can collect while **considering the two key factors**: the robot's ability to neutralize robbers and the path it takes through the grid. We use **dynamic programming** to break the problem down into manageable subproblems.

### Key Ideas:
1. **State Representation**: 
   - At any cell `(i, j)`, we need to remember:
     - The **maximum coins** collected so far.
     - The number of **neutralizations** used so far (since the robot can neutralize up to 2 robbers).

2. **Transitions**:
   - From any cell, the robot can either move **right** or **down**.
   - If the robot encounters a **robber** (negative coins), it has two choices:
     1. **Neutralize** the robber (if it hasn't used both neutralizations).
     2. **Take the penalty** and lose coins.
   - If there's no robber, the robot just **gains coins**.

3. **Goal**:
   - Maximize the **total coins** collected when reaching the bottom-right corner of the grid.

### Intuition:
- The robot needs to consider **all possible paths** to reach the destination while deciding when to **neutralize robbers**.
- It uses a **3D DP table** to track:
  - The maximum coins collected.
  - The number of neutralizations used (0, 1, or 2).
- The result is the maximum value from the last cell `(m-1, n-1)` considering all neutralizations (0, 1, or 2).

By breaking down the problem into these subproblems and considering neutralization as an optional decision at each step, the robot can ensure it makes the **optimal decisions** at each point to maximize its profit.
# Approach
To solve the problem efficiently, we use a **Dynamic Programming (DP)** approach that keeps track of the maximum coins the robot can collect while considering all possible paths and the option to neutralize robbers. Here's the approach in detail:

### 1. **State Representation**:
We define a 3D DP array `dp[i][j][k]`:
- `i` represents the row index.
- `j` represents the column index.
- `k` represents the number of robbers neutralized up to that point (0, 1, or 2).
  
The value of `dp[i][j][k]` holds the maximum coins collected at cell `(i, j)` with exactly `k` neutralizations used.

### 2. **Initialization**:
- **Starting Point**: The robot begins at the top-left corner of the grid `(0, 0)`. We initialize the DP table based on whether the starting cell contains a robber or not:
  - If `coins[0][0] < 0`, we initialize `dp[0][0][1] = 0` (since neutralizing the first robber would avoid the coin loss).
  - If `coins[0][0] >= 0`, we initialize `dp[0][0][0] = coins[0][0]` (the robot gains coins at the start).

### 3. **Transitions**:
From each cell `(i, j)`, the robot can move either **right** or **down**:
- **Moving Right**: If the robot moves to cell `(i, j+1)`:
  - If the cell contains a **non-negative number** (coins), the robot simply collects those coins.
  - If the cell contains a **negative number** (robber), the robot can either:
    - **Neutralize** the robber (if it has neutralizations left).
    - **Take the penalty** (losing the coins).
- **Moving Down**: The same logic applies when moving down to cell `(i+1, j)`.

For each move, the DP value is updated considering both options: neutralize or take the penalty.

### 4. **Final Result**:
The robot reaches the bottom-right corner `(m-1, n-1)`. We check the maximum value of `dp[m-1][n-1][0]`, `dp[m-1][n-1][1]`, and `dp[m-1][n-1][2]` because the robot could have neutralized 0, 1, or 2 robbers on the path.

### 5. **Time and Space Complexity**:
- **Time Complexity**: \(O(m \times n \times 3)\), where `m` is the number of rows, `n` is the number of columns, and `3` is the number of possible neutralization states.
- **Space Complexity**: \(O(m \times n \times 3)\), as we need to store the DP table with 3 possible neutralization states for each cell.

### Conclusion:
By maintaining a dynamic programming table that considers the maximum coins collected and the number of neutralizations used, we can efficiently compute the maximum profit the robot can make while traversing the grid. This approach ensures that the robot makes the optimal decision at each step, balancing the trade-off between neutralizing robbers and collecting coins.
# Complexity
- Time complexity:
The time complexity depends on the size of the grid and the number of states (neutralizations) we are tracking.

Grid size: The grid has m rows and n columns, so there are a total of m * n cells in the grid.
States: For each cell (i, j), we track 3 possible states based on the number of neutralizations used (0, 1, and 2).
Thus, for each of the m * n cells, we are considering 3 possible neutralization states. For each state, the robot can move either right or down, and we are updating the DP table based on the conditions (whether to neutralize a robber or not, and the coins gained or lost).

For each cell: We are updating the value for 3 states, and each update takes constant time 
𝑂(1).
Total cells: There are m * n cells.
States per cell: There are 3 possible neutralization states for each cell.
Therefore, the overall time complexity is:

𝑂(𝑚×𝑛×3) = 𝑂(𝑚×𝑛)
Since the factor of 3 is constant, it doesn't affect the overall complexity.

- Space complexity:
Space Complexity: 
𝑂(𝑚×𝑛)
# Code
```cpp []
class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();

        // DP array: dp[i][j][k] stores the max coins at (i, j) with k neutralizations used
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, INT_MIN)));

        // Initialization for the starting cell
        dp[0][0][0] = coins[0][0]; // Start without neutralization
        if (coins[0][0] < 0) dp[0][0][1] = 0; // Neutralize if starting with a robber

        // Fill the DP table
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    if (dp[i][j][k] == INT_MIN) continue;

                    // Move right
                    if (j + 1 < n) {
                        int nextCell = coins[i][j + 1];

                        // Case 1: Don't neutralize
                        dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k] + nextCell);

                        // Case 2: Neutralize if it's a robber
                        if (nextCell < 0 && k + 1 <= 2) {
                            dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k]);
                        }
                    }

                    // Move down
                    if (i + 1 < m) {
                        int nextCell = coins[i + 1][j];

                        // Case 1: Don't neutralize
                        dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + nextCell);

                        // Case 2: Neutralize if it's a robber
                        if (nextCell < 0 && k + 1 <= 2) {
                            dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k]);
                        }
                    }
                }
            }
        }

        // Get the maximum value at the bottom-right corner considering all neutralization states
        return max({dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});
    }
};

```
['C++']