Maximum Amount of Money Robot Can Earn - Memoized Dynamic Programming Solution | Beats 100% 💰
IntuitionThe problem is a variation of the classic path-finding problem in a grid with constraints. The robot must maximize its profit while considering two key

### Intuition  
The problem is a variation of the classic path-finding problem in a grid with constraints. The robot must maximize its profit while considering two key rules:
1. Robbers (cells with negative values) decrease profit.
2. The robot can neutralize up to two robbers during its journey, turning their penalties into neutral cells.  

The solution uses **recursive dynamic programming (DP)** to compute the maximum profit while traversing the grid.  

### Key Insight:  
- The robot has **two states** to track:  
  1. Its current position in the grid `(i, j)`.  
  2. The remaining number of robbers it can neutralize (`available`).  
- Using a 3D DP array, `dp[i][j][available]`, we store the maximum profit the robot can achieve at each cell `(i, j)` with a specific number of neutralizations remaining.  

### Approach  
1. **Recursive Function (DFS):**  
   - Base Case:  
     - If the robot reaches the bottom-right corner `(m - 1, n - 1)`, return the value of the cell considering its neutralization state.  
   - Recursive Transition:  
     - At each cell `(i, j)`, calculate the profit for the next moves (`right` and `down`) under the following conditions:  
       1. If the cell has a robber and the robot can neutralize it.  
       2. If the cell has a robber and the robot cannot neutralize it.  
       3. If the cell has no robber.  
   - Use memoization to avoid redundant calculations.  

2. **Initialization:**  
   - Start from the top-left corner `(0, 0)` with two available neutralizations.  

3. **Result:**  
   - Return the maximum profit stored in `dp[0][0][2]`.  

### Dry Run:  
#### Problem:
Find the maximum profit for the robot while moving from the top-left `(0, 0)` to the bottom-right `(2, 2)` with at most two robber neutralizations available.  

#### Input:
`coins = [[0, 1, -1], [1, -2, 3], [2, -3, 4]]`  
`available = 2`  

#### DP Table:
- A 3D DP table `dp[i][j][available]` is initialized to `INT_MIN` to store maximum profit for each cell `(i, j)` with a specific number of neutralizations remaining.

---

### Step-by-Step Dry Run:

**Start at `(0, 0)` with `available = 2`:**  
1. Current cell value = `0` (neutral).  
2. Move `Right (0, 1)` or `Down (1, 0)`.  

---

**Move to `(0, 1)` with `available = 2`:**  
1. Current cell value = `1` (neutral).  
2. Add `1` to profit. Total profit so far = `1`.  
3. Move `Right (0, 2)` or `Down (1, 1)`.  

---

**Move to `(0, 2)` with `available = 2`:**  
1. Current cell value = `-1` (robber).  
2. Neutralize robber (`available = 1`), profit remains `1`.  
   - Move `Down (1, 2)`.  
3. Do not neutralize robber (`available = 2`), profit = `0`.  
   - Move `Down (1, 2)`.

---

**Move to `(1, 2)` with `available = 1`:**  
1. Current cell value = `3` (neutral).  
2. Add `3` to profit. Total profit = `4`.  
3. Move `Down (2, 2)`.

---

**Move to `(2, 2)` with `available = 1`:**  
1. Current cell value = `4` (neutral).  
2. Add `4` to profit. Total profit = `8`.  
3. Reached the destination.  

Backtrack to consider all possible paths.

---

**Move to `(1, 2)` with `available = 2`:**  
1. Current cell value = `3` (neutral).  
2. Add `3` to profit. Total profit = `3`.  
3. Move `Down (2, 2)`.

---

**Move to `(2, 2)` with `available = 2`:**  
1. Current cell value = `4` (neutral).  
2. Add `4` to profit. Total profit = `7`.  

---

**Move to `(1, 1)` with `available = 2`:**  
1. Current cell value = `-2` (robber).  
2. Neutralize robber (`available = 1`), profit remains `1`.  
   - Move `Right (1, 2)` or `Down (2, 1)`.  
3. Do not neutralize robber (`available = 2`), profit = `-1`.  
   - Move `Right (1, 2)` or `Down (2, 1)`.

---

**Move to `(1, 1)` with `available = 1`:**  
1. Repeating similar calculations, the maximum profit path is determined.

---

### Final DP Table:
After evaluating all paths, the DP table stores the following maximum profits:  
    `dp = [ [[8, 8, 8], [7, 7, 7], [6, 6, 6]], [[8, 8, 8], [7, 7, 7], [6, 6, 6]], [[8, 8, 8], [7, 7, 7], [6, 6, 6]] ]`


---

### Output:
The robot's maximum profit is `8`.  

### Explanation of Optimal Path:
1. `(0, 0)` → `(0, 1)` → `(0, 2)` [Neutralize robber] → `(1, 2)` → `(2, 2)`.  
2. Along this path, robbers were neutralized strategically to maximize the total profit.  
3. Total profit: `0 + 1 + 0 (neutralized) + 3 + 4 = 8`.  

---


### Complexity  
- Time Complexity: `O(m * n * k)` 
   where \( m, n \) are the grid dimensions, and \( k = 3 \) (neutralization states).  

- Space Complexity: `O(m * n * k)`  
  for the DP table.  

---
### Code  
```cpp
class Solution {
public:
    int dfs(vector<vector<int>>& coins, int i, int j, int available,
            vector<vector<vector<int>>>& dp) {
        // Base case: Reached bottom-right corner
        if (i == coins.size() - 1 && j == coins[0].size() - 1) {
            if (coins[i][j] >= 0) return coins[i][j];
            if (coins[i][j] < 0 && available > 0) return 0;
            return coins[i][j];
        }

        // Out of bounds
        if (i >= coins.size() || j >= coins[0].size()) return INT_MIN;

        // Memoization
        if (dp[i][j][available] != INT_MIN) return dp[i][j][available];

        int profit = INT_MIN;

        // Handle robbers and neutralization
        if (coins[i][j] < 0) {
            if (available > 0) {
                // Neutralize robber
                profit = max(profit, dfs(coins, i + 1, j, available - 1, dp));
                profit = max(profit, dfs(coins, i, j + 1, available - 1, dp));
            }
            // Do not neutralize
            profit = max(profit, coins[i][j] + dfs(coins, i + 1, j, available, dp));
            profit = max(profit, coins[i][j] + dfs(coins, i, j + 1, available, dp));
        } else {
            // Normal cell
            profit = max(profit, coins[i][j] + dfs(coins, i + 1, j, available, dp));
            profit = max(profit, coins[i][j] + dfs(coins, i, j + 1, available, dp));
        }

        return dp[i][j][available] = profit;
    }

    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        int available = 2;  // Robber neutralization limit

        // 3D DP table: dp[i][j][available]
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, INT_MIN)));

        return dfs(coins, 0, 0, available, dp);
    }
};

['Dynamic Programming', 'Recursion', 'Memoization', 'Matrix', 'C++']