Recursive Approach || Tabulation Method || and Top 100% Solution✅🔥
IntuitionThe problem involves finding the maximum amount you can collect from a grid of coins, starting from the bottom-right corner (target) and moving to the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves finding the maximum amount you can collect from a grid of coins, starting from the bottom-right corner (target) and moving to the top-left corner. You have three chances to neutralize negative values if you encounter any. The goal is to maximize the collected value while considering these opportunities to "overwrite" negative coins.

Base Case:

The bottom-right corner of the grid has either a positive or negative value. Depending on whether it’s negative, you either store the value itself if you have no more chances left (k == 0) or you store 0 if you have remaining chances.
Recursive Relation:

From each cell, you can move right or down. If you encounter a negative value, you can either:
Use one of your remaining chances to overwrite it and continue, or
Ignore it if you have no chances left.
The approach is to calculate the maximum possible value you can collect by making these choices recursively.


# Approach
<!-- Describe your approach to solving the problem. -->
The approach to solving this problem involves using dynamic programming (DP) to keep track of the maximum amount of coins that can be collected starting from the bottom-right corner and moving towards the top-left corner of the grid. The DP table is a 3D matrix, where each cell dp[i][j][k] represents the maximum coins collected at position (i, j) with k chances left to overwrite negative values. We iterate through the grid in a bottom-up fashion, filling the DP table by considering the possible moves to the right or down from each cell. The base case is handled at the bottom-right corner, where we either take the coin value directly or ignore it based on the availability of chances. For cells with negative coins, if we have available chances, we can overwrite the negative value; otherwise, we skip it. Finally, the result is found at dp[0][0][2], which gives the maximum coins that can be collected starting from the top-left corner with two chances remaining.

# Complexity
**- Time complexity:**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
   - The DP table has dimensions m x n x 3, where m is the number of rows and n is the number of columns.
   - The table will be filled in O(m * n * 3), leading to O(m * n) time co

**- Space complexity:**
- The DP table consumes O(m * n * 3) space, leading to O(m * n) space complexity.

# Code
**Memorizarion**
```cpp []

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();
        int const NEG_INF = -1e9;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, NEG_INF)));

        for (int k = 0; k < 3; k++) { // Iterate over chances
            for (int i = m - 1; i >= 0; i--) { // Iterate rows in reverse
                for (int j = n - 1; j >= 0; j--) { // Iterate columns in reverse
                    // Base case: Bottom-right cell
                    if (i == m - 1 && j == n - 1) {
                        if (coins[i][j] < 0) {
                            dp[i][j][k] = (k == 0) ? coins[i][j] : 0; // Use chance if available
                        } else {
                            dp[i][j][k] = coins[i][j];
                        }
                        continue;
                    }

                    int right = NEG_INF, down = NEG_INF;

                    // Neutralize negatives if chances are available
                    if (coins[i][j] < 0 && k > 0) {
                        right = (j + 1 < n) ? dp[i][j + 1][k - 1] : NEG_INF;
                        down = (i + 1 < m) ? dp[i + 1][j][k - 1] : NEG_INF;
                    }

                    // Add current cell value for positive cases
                    right = max(right, (j + 1 < n) ? coins[i][j] + dp[i][j + 1][k] : NEG_INF);
                    down = max(down, (i + 1 < m) ? coins[i][j] + dp[i + 1][j][k] : NEG_INF);

                    dp[i][j][k] = max(right, down); // Corrected this line
                }
            }
        }

        return dp[0][0][2]; // Return the result from the top-left corner
    }
};

```
# Code
**Recursive approach**
```cpp []
class Solution {
public:
    int f(vector<vector<int>> &coins,int chances,int row,int col,int m,int n,vector<vector<vector<int>>> &dp){
        if (row == m - 1 && col == n - 1) {
            if (coins[row][col] < 0 ) 
                if( chances <= 0)
                    return coins[row][col]; // No chance left to handle negative
                else
                    return 0;
            return coins[row][col];
        }

        // Out-of-bounds condition
        if (row >= m || col >= n) return -1e9;

         if (dp[row][col][chances] != INT_MIN)
            return dp[row][col][chances];

        int right=-1e9,down=-1e9;
        if (coins[row][col] < 0 && chances > 0) {
            right = f(coins, chances - 1, row, col + 1, m, n,dp);
            down = f(coins, chances - 1, row + 1, col, m, n,dp);
        }

        right = max(right, coins[row][col] + f(coins, chances, row, col + 1, m, n,dp));
        down = max(down, coins[row][col] + f(coins, chances, row + 1, col, m, n,dp));
        return dp[row][col][chances]=max(right, down);

    }
    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,INT_MIN)));
        return f(coins,2,0,0,m,n,dp);
    }
};
```



please upvote 😊 



['C++']