DP Approach || 3DP Problem
IntuitionThe problem involves finding the maximum amount of coins that can be collected while moving through a 2D grid. The grid contains positive and negative
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves finding the maximum amount of coins that can be collected while moving through a 2D grid. The grid contains positive and negative values, and we are allowed to skip up to two negative values. The goal is to maximize the sum of the collected coins while adhering to the constraints.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Dynamic Programming (DP) Setup**:
   - Use a 3D DP array `dp[i][j][k]` where:
     - `i` and `j` represent the current cell in the grid.
     - `k` represents the number of negative values skipped so far (0, 1, or 2).
   - Initialize the DP array with `INT_MIN` to represent unreachable states.
2. **Base Case**:
   - Start at the top-left corner of the grid. If the cell contains a positive value, initialize `dp[0][0][0]` with that value. If it contains a negative value, initialize `dp[0][0][1]` with 0 (indicating one skip).
3. **DP Transition**:
   - Traverse the grid row-wise and column-wise.
   - For each cell, update the DP values based on the values from the left cell (`dp[i][j-1][k]`) and the top cell (`dp[i-1][j][k]`).
   - If the current cell contains a positive value, add it to the DP value.
   - If the current cell contains a negative value, update the DP value for the next skip count (`k + 1`).
4. **Result Extraction**:
   - The result is the maximum value among `dp[m-1][n-1][k]` for `k = 0, 1, 2`.

# Complexity
- **Time complexity**: $$O(m \times n \times 3)$$
  - We traverse the entire grid of size `m x n` and update the DP array for 3 possible skip counts.
- **Space complexity**: $$O(m \times n \times 3)$$
  - The DP array requires space proportional to `m x n x 3`.

# Code
```cpp
#define ll long long
#define vvvi vector<vector<vector<int>>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define ll long long
class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        ll m = coins.size();
        ll n = coins[0].size();

        // Initialize DP array with INT_MIN
        vvvi dp(m, vvi(n, vi(3, INT_MIN)));

        // Base case: starting cell
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0][0][1] = 0;
        }

        // Fill the first row
        for (int j = 1; j < n; j++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[0][j - 1][k] == INT_MIN) continue;
                if (coins[0][j] >= 0) {
                    dp[0][j][k] = max(dp[0][j][k], dp[0][j - 1][k] + coins[0][j]);
                } else {
                    dp[0][j][k] = max(dp[0][j][k], dp[0][j - 1][k] + coins[0][j]);
                }
                if (k < 2 && coins[0][j] < 0) {
                    dp[0][j][k + 1] = max(dp[0][j][k + 1], dp[0][j - 1][k]);
                }
            }
        }

        // Fill the first column
        for (int i = 1; i < m; i++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[i - 1][0][k] == INT_MIN) continue;
                if (coins[i][0] >= 0) {
                    dp[i][0][k] = max(dp[i][0][k], dp[i - 1][0][k] + coins[i][0]);
                } else {
                    dp[i][0][k] = max(dp[i][0][k], dp[i - 1][0][k] + coins[i][0]);
                }
                if (k < 2 && coins[i][0] < 0) {
                    dp[i][0][k + 1] = max(dp[i][0][k + 1], dp[i - 1][0][k]);
                }
            }
        }

        // Fill the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                for (int k = 0; k <= 2; k++) {
                    if (dp[i][j - 1][k] != INT_MIN) {
                        if (coins[i][j] >= 0) {
                            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + coins[i][j]);
                        } else {
                            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + coins[i][j]);
                        }
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j - 1][k]);
                        }
                    }
                    if (dp[i - 1][j][k] != INT_MIN) {
                        if (coins[i][j] >= 0) {
                            dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + coins[i][j]);
                        } else {
                            dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + coins[i][j]);
                        }
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i - 1][j][k]);
                        }
                    }
                }
            }
        }

        // Find the maximum result among the last cell's DP values
        int result = INT_MIN;
        for (int k = 0; k <= 2; k++) {
            result = max(result, dp[m - 1][n - 1][k]);
        }

        return result;
    }
};
['C++']