💢Recursive ,Memoisation, Tabulation (Striver Based)💢✅💯 Clean Code Every Approach Explained💥🔥💫
Problem StatementGiven a 2D grid coins where each cell contains an integer representing coins (positive or negative), find the maximum amount of coins that can

## Problem Statement
Given a 2D grid `coins` where each cell contains an integer representing coins (positive or negative), find the maximum amount of coins that can be collected from the top-left corner `(0, 0)` to the bottom-right corner `(m-1, n-1)`. You are allowed to negate the value of at most 2 negative coins during the path.

---

## Recursive Approach
Gives TLE Because of high Time complexity
### Explanation
1. **Base Case**:
   - If the current cell is `(m-1, n-1)` (destination):
     - If the coin is negative:
       - Negate it if `rem > 0`.
       - Otherwise, take it as is.
     - If the coin is positive, add its value.
   - Return the computed value for the destination cell.
   
2. **Out of Bounds Check**:
   - If the cell is out of bounds, return a large negative value (`-1e9`), representing an invalid path.

3. **Recursive Exploration**:
   - From the current cell `(i, j)`, move **right** or **down**.
   - If the current cell has a negative value and `rem > 0`, explore both:
     - Negating the value and reducing `rem`.
     - Keeping the value and retaining `rem`.

4. **Return the Maximum**:
   - Return the maximum value between the paths explored.

### Code
```cpp
class Solution 
{
public:
    int helperF(int i, int j, int rem, int n, int m, vector<vector<int>>& coins) {
        if (i == n - 1 && j == m - 1) { // Base Case
            if (coins[i][j] < 0)  
                return (rem > 0) ? 0 : coins[i][j];
            else 
                return coins[i][j];
        }

        if (i >= n || j >= m) // Out of Bounds
            return -1e9;

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

        // Handle negative coin
        if (coins[i][j] < 0 && rem > 0) {
            right = helperF(i, j + 1, rem - 1, n, m, coins);
            down = helperF(i + 1, j, rem - 1, n, m, coins);
        }

        // Regular moves without negation
        right = max(right, coins[i][j] + helperF(i, j + 1, rem, n, m, coins));
        down = max(down, coins[i][j] + helperF(i + 1, j, rem, n, m, coins));

        return max(right, down);
    }

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

---


## Memoization Approach

### Explanation
1. **Base Case**:
   - If the current cell is `(m-1, n-1)` (destination):
     - If the coin is negative:
       - Negate it if `rem > 0`.
       - Otherwise, take it as is.
     - If the coin is positive, add its value.
   - Return the computed value for the destination cell.
   
2. **Out of Bounds Check**:
   - If the cell is out of bounds, return a large negative value (`-1e9`), representing an invalid path.

3. **Memoization**:
   - Use a 3D DP table `dp[i][j][rem]` to store intermediate results.
   - Before computing the result for `(i, j)` with `rem` negations, check if the value is already computed.
   - If computed, return the value. Otherwise, compute, store, and return.

4. **Recursive Exploration**:
   - From the current cell `(i, j)`, move **right** or **down**.
   - Handle negative values by optionally negating them if `rem > 0`.

5. **Return the Maximum**:
   - Return the maximum value between the paths explored.

### Code
```cpp
class Solution 
{
public:
    int helperF(int i, int j, int rem, int n, int m, vector<vector<int>>& coins, vector<vector<vector<int>>>& dp) {
        if (i == n - 1 && j == m - 1) { // Base Case
            if (coins[i][j] < 0)  
                return (rem > 0) ? 0 : coins[i][j];
            else 
                return coins[i][j];
        }

        if (i >= n || j >= m) // Out of Bounds
            return -1e9;

        if (dp[i][j][rem] != -1) // Return cached result
            return dp[i][j][rem];

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

        // Handle negative coin
        if (coins[i][j] < 0 && rem > 0) {
            right = helperF(i, j + 1, rem - 1, n, m, coins, dp);
            down = helperF(i + 1, j, rem - 1, n, m, coins, dp);
        }

        // Regular moves without negation
        right = max(right, coins[i][j] + helperF(i, j + 1, rem, n, m, coins, dp));
        down = max(down, coins[i][j] + helperF(i + 1, j, rem, n, m, coins, dp));

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

    int maximumAmount(vector<vector<int>>& coins) {
        int n = coins.size();
        int m = coins[0].size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(3, -1)));
        return helperF(0, 0, 2, n, m, coins, dp);   
    }
};

```

---
# Tabulation Approach

## Explanation

### 1. **DP Table Initialization**
   - Use a 3D DP table `dp[i][j][rem]`:
     - `dp[i][j][rem]` represents the maximum amount of coins collectable from cell `(i, j)` to the destination `(m-1, n-1)` with `rem` negations of negative coins left.
   - Initialize the DP table with a very small value `-1e9` to indicate unvisited states.

---

### 2. **Base Case**
   - For the destination cell `(m-1, n-1)`:
     - If the coin value is negative:
       - Use the negation if `rem > 0` (set the value to `0`).
       - Otherwise, take the coin value as it is.
     - If the coin value is positive, add it directly to the DP table.

---

### 3. **Iterative Calculation**
   - Traverse the grid from **bottom-right** to **top-left**.
   - For each cell `(i, j)` and each possible value of `rem`:
     - **Right Move**:
       - If moving right `(i, j+1)` is within bounds:
         - Add the coin value from the current cell to `dp[i][j+1][rem]`.
         - If `rem > 0`, consider negating a negative coin (`dp[i][j+1][rem-1]`).
     - **Down Move**:
       - If moving down `(i+1, j)` is within bounds:
         - Add the coin value from the current cell to `dp[i+1][j][rem]`.
         - If `rem > 0`, consider negating a negative coin (`dp[i+1][j][rem-1]`).
     - Store the maximum value between the two possible moves in `dp[i][j][rem]`.

---

### 4. **Result**
   - The final result is stored in `dp[0][0][2]`, which represents the maximum coins collectable starting from `(0, 0)` with 2 negations allowed.

---

## Code

```cpp
class Solution 
{
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, -1e9))); // Initialize DP table

        for (int rem = 0; rem < 3; rem++) { // Iterate through remaining negations
            for (int i = m - 1; i >= 0; i--) { // Bottom to top
                for (int j = n - 1; j >= 0; j--) { // Right to left
                    if (i == m - 1 && j == n - 1) { // Base Case
                        dp[i][j][rem] = rem > 0 ? max(0, coins[i][j]) : coins[i][j];
                        continue;
                    }

                    int maxi = -1e9; // Initialize maximum value

                    // Move Down
                    if (i + 1 < m) {
                        maxi = max(maxi, coins[i][j] + dp[i + 1][j][rem]);
                        if (rem > 0) maxi = max(maxi, dp[i + 1][j][rem - 1]);
                    }

                    // Move Right
                    if (j + 1 < n) {
                        maxi = max(maxi, coins[i][j] + dp[i][j + 1][rem]);
                        if (rem > 0) maxi = max(maxi, dp[i][j + 1][rem - 1]);
                    }

                    dp[i][j][rem] = maxi; // Update DP table
                }
            }
        }

        return dp[0][0][2]; // Result stored in starting position with 2 negations
    }
};

```

---

# Time and Space Complexities of All Approaches

| Approach       | Time Complexity        | Space Complexity       | Explanation                                                                 |
|----------------|-------------------------|-------------------------|-----------------------------------------------------------------------------|
| **Recursive**  | \(O(2^{(m+n)})\)       | \(O(m + n)\)           | Explores all possible paths with redundant computations, uses recursion stack. |
| **Memoization**| \(O(m*n*3)\) | \(O(m*n*3)\) + \(O(m + n)\) | Avoids redundant computations by storing results of subproblems, but requires extra space for memoization table. |
| **Tabulation** | \(O(m*n*3)\) | \(O(m*n*3)\) | Iterative approach that systematically fills the DP table, no recursion stack used. |

- **\(m\)**: Number of rows in the grid.
- **\(n\)**: Number of columns in the grid.
- **3**: Constant number of possible remaining negations (\(rem = 0, 1, 2\)).

### Key Notes:
1. **Recursive** approach is the least efficient due to exponential time complexity and lack of caching.
2. **Memoization** optimizes the recursive approach by reducing redundant calculations, but still uses recursion stack.
3. **Tabulation** is the most efficient and systematic approach with iterative computation and avoids stack overhead.

---

![upcat.png](https://assets.leetcode.com/users/images/3df17ef8-3e27-401d-bd9c-530033118ad0_1736699418.5108464.png)


['C++']