Python DFS Solution
Intuition for the ProblemThe goal is to maximize the total amount collected from a grid of coins, with the ability to neutralize up to 2 negative coins. This is
# Intuition for the Problem

The goal is to maximize the total amount collected from a grid of coins, with the ability to neutralize up to 2 negative coins. This is achieved by using a recursive Depth-First Search (DFS) approach with memoization to efficiently explore all possible paths from the top-left to the bottom-right corner.

## Key Observations
1. **Path Constraints:**
   - At each step, you can move either **down** or **right** within the grid.
   - The recursion ends when we reach the bottom-right corner or go out of bounds.

2. **Handling Negative Coins:**
   - If a cell contains a negative coin, we can either:
     - **Neutralize it** (if we haven't already neutralized 2 coins).
     - **Take it as is** without neutralizing.
   - If neutralization is chosen, it counts as one of the two neutralization opportunities.

3. **Decision-Making:**
   - At each cell, we calculate the maximum coins we can collect by considering:
     - The value obtained if the current coin is **not neutralized**.
     - The value obtained if the current coin is **neutralized** (if allowed).
   - We take the maximum of these two values.

4. **Dynamic Programming with Memoization:**
   - To avoid redundant calculations, we use `lru_cache` to memoize the results of subproblems.
   - The state of our recursion is defined by `(row, column, k)`, where:
     - `row` and `column` represent the current position in the grid.
     - `k` represents the number of coins already neutralized.

## Base Cases
1. If we move out of the grid bounds (`r >= rowLen` or `c >= colLen`), the result is `0`.
2. If we are at the bottom-right corner:
   - If the coin is negative and can be neutralized, decide accordingly.
   - Otherwise, simply take the coin's value.

## Recursive Relation
At each position `(r, c)`:
- Let `notNeutralized` be the result of taking the coin as is.
- Let `neutralized` be the result of neutralizing the coin (if it's negative and `k < 2`).
- The result for `(r, c, k)` is:max(notNeutralized, neutralized)

## Complexity Analysis
1. **Time Complexity:**
 - Since there are `rowLen * colLen` cells and `k` can take at most 3 states (`0, 1, 2`), the number of unique states is `O(rowLen * colLen * 3)`.
 - Each state is computed once due to memoization, making the time complexity approximately `O(rowLen * colLen)`.

2. **Space Complexity:**
 - The memoization cache and the recursive call stack take up `O(rowLen * colLen * 3)` space.

## Conclusion
The solution efficiently explores all possible paths in the grid using recursion and memoization, while carefully managing the use of neutralizations to maximize the total coins collected.



# Code
```python3 []
class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        rowLen = len(coins)
        colLen = len(coins[0])

        @lru_cache(None)
        def dfs(r,c,k):
            if r>= rowLen or c >=colLen:
                return float('-inf')
            if r == rowLen -1 and c == colLen -1:
                if coins[r][c] < 0:
                    if k < 2:
                        return 0
                return coins[r][c]
            notNeutralized = coins[r][c] + max(dfs(r+1,c,k),dfs(r,c+1,k))
            neutralized = float('-inf')
            if coins[r][c] < 0 and k < 2:
                neutralized = 0 + max(dfs(r+1,c,k+1),dfs(r,c+1,k+1)) 
            else:
                neutralized = coins[r][c] + max(dfs(r+1,c,k),dfs(r,c+1,k)) 
            return max(neutralized,notNeutralized)
        return dfs(0,0,0)
```
['Depth-First Search', 'Memoization', 'Python3']