3418. Maximum Amount of Money Robot Can Earn | DP - Memoization Approach Explained ✨✅
Navigate the Coin Grid: Maximize Profits with Smart Moves!Problem IntuitionThe problem involves navigating an n X m grid where each cell contains coins (positiv
# **Navigate the Coin Grid: Maximize Profits with Smart Moves!**

### **Problem Intuition**
The problem involves navigating an n X m grid where each cell contains coins (positive or negative). The robot starts from the **top-left corner** and must reach the **bottom-right corner**, moving **either right or down**. Key challenges include:

1. **Maximizing total coins** while traveling through the grid.
2. **Neutralizing robbers** in at most 2 cells to avoid losing coins.
3. Using **Dynamic Programming (DP)** to systematically explore and optimize paths.

The solution requires us to carefully decide:
- **When to neutralize robbers**, using the two opportunities available.
- **Which path (down/right)** gives the maximum total coins.

---

### **Approach**
To solve the problem efficiently, we use **Dynamic Programming with recursion**. Let's break this approach into clear steps:

#### **Step 1: State Representation**
Define a function `help(i, j, rem, n, m, coins, dp)`:
- \(i, j\): Current cell position.
- \(rem\): Remaining opportunities to neutralize robbers.
- \(n, m\): Grid dimensions.
- `coins`: The grid with coin values.
- `dp[i][j][rem]`: Memoization table that stores the maximum coins obtainable from position \((i, j)\) with `rem` robber-neutralization opportunities left.

#### **Step 2: Recursive Formula**
1. **Base Case:**
   - If \((i, j) = (n-1, m-1)\) (bottom-right corner):
     - Return the coin value of the cell, adjusting for robbers if needed.
   - If out of bounds, return \(-\infty\) to indicate an invalid path.

2. **Recursive Cases:**
   - Explore **right** and **down** paths from the current cell:
     - **If the cell has a robber (\(coins[i][j] < 0\))**, decide:
       - Use one neutralization opportunity (if available) and ignore the loss.
       - Accept the loss without neutralizing.
     - Add the current cell value to the results of the right or down path.
   - Store and return the maximum of the two options.

#### **Step 3: DP Table Initialization**
Use a 3D DP table, `dp[n][m][3]`:
- \(n, m\): Grid dimensions.
- 3 layers for `rem` values (0, 1, or 2 neutralizations available).

#### **Step 4: Optimization**
- **Memoization:** Avoid recomputing states by caching results in the DP table.
- **Iterate efficiently** through valid paths, minimizing redundant checks.

---
### **Code Explanation**
```cpp []

#define vi vector<int>
#define vvi vector<vi>

class Solution {
public:
    // Helper function to calculate max coins from (i, j) with 'rem' neutralizations left
    int help(int i, int j, int rem, int n, int m, vvi& coins, vector<vvi>& dp) {
        // Base case: reached bottom-right corner
        if (i == n - 1 && j == m - 1) {
            if (coins[i][j] < 0) {
                // If this is a robber cell, neutralize if rem > 0
                return (rem > 0) ? 0 : coins[i][j];
            } else {
                return coins[i][j];
            }
        }

        // Boundary check: If out of bounds, return -infinity
        if (i >= n || j >= m)
            return -1e9;

        // If already computed, return cached result
        if (dp[i][j][rem] != INT_MIN)
            return dp[i][j][rem];

        int right = -1e9, down = -1e9;

        // If current cell is a robber, consider neutralization options
        if (coins[i][j] < 0) {
            if (rem > 0) { // Neutralize the robber
                right = help(i, j + 1, rem - 1, n, m, coins, dp);
                down = help(i + 1, j, rem - 1, n, m, coins, dp);
            }
        }

        // Take the current cell value + max of right/down without neutralization
        right = max(right, coins[i][j] + help(i, j + 1, rem, n, m, coins, dp));
        down = max(down, coins[i][j] + help(i + 1, j, rem, n, m, coins, dp));

        // Store and return the result
        return dp[i][j][rem] = max(right, down);
    }

    int maximumAmount(vector<vector<int>>& coins) {
        int n = coins.size(), m = coins[0].size();

        // Initialize 3D DP table with INT_MIN
        vector<vvi> dp(n + 1, vvi(m + 1, vi(3, INT_MIN)));

        // Start recursion from the top-left corner with 2 neutralizations available
        return help(0, 0, 2, n, m, coins, dp);
    }
};
```


---

### **Complexity Analysis**
1. **Time Complexity:**
   - O(n⋅m⋅3)=O(n⋅m): We compute for every cell  (n⋅m) and for 3 neutralization states.
   - Memoization avoids redundant calculations.

2. **Space Complexity:**
   - O(n⋅m⋅3)=O(n⋅m): Space for the 3D DP table.


---

## **PLEASE UPVOTE IF YOU LIKED IT ✅** 
['Dynamic Programming', 'Memoization', 'Python', 'C++', 'Java']