Top down approach - memoization - beats 100% - python3
IntuitionThe problem requires us to maximize the coins collected along a path from the top-left to the bottom-right of a grid. Multiple paths are possible, and
## Intuition
The problem requires us to maximize the coins collected along a path from the top-left to the bottom-right of a grid. Multiple paths are possible, and we can neutralize up to two negative cells, which adds complexity to the problem.

This means we need to explore all paths and compute the maximum coins collected. To efficiently solve this, we use a **top-down dynamic programming (DP)** approach with memoization. This approach allows us to avoid redundant calculations by caching results for overlapping subproblems.

## Approach
We define a recursive function `dfs(i, j, k)`:
- `i`: Row index of the current cell.
- `j`: Column index of the current cell.
- `k`: Remaining neutralizations available.

### Steps:
1. **Base Cases**:
   - If `(i, j)` is out of bounds, return a very small value (e.g., `-inf`) since the path is invalid.
   - If `(i, j)` is the bottom-right corner, return the value of the cell, considering whether neutralization is needed.

2. **Recursive Step**:
   - At each cell, we have two choices:
     1. Move **down**: Explore the path starting at `(i+1, j)`.
     2. Move **right**: Explore the path starting at `(i, j+1)`.
   - For each choice, we also decide whether to use a neutralization if the cell's value is negative (`coins[i][j] < 0`).

3. **Memoization**:
   - Store the result of `dfs(i, j, k)` in a cache to avoid recalculating results for the same state `(i, j, k)`.

4. **Initial Call**:
   - Start the recursion with `dfs(0, 0, 2)`, representing the top-left cell with 2 neutralizations available.

### Key Idea:
The DP function computes the maximum coins that can be collected starting from cell `(i, j)` with `k` neutralizations remaining. The results are cached to optimize performance.

## Complexity
### Time Complexity:
- Each cell `(i, j)` is visited for all possible values of `k` (0, 1, 2).
- Total number of states: \(O(m \* n \* 3)\).
- Each state is computed in \(O(1)\), so the overall time complexity is: O(m \* n)

### Space Complexity:
1. **Memoization Table**:
   - Stores \(O(m \* n \*times* 3)\) states.
2. **Recursion Stack**:
   - The maximum recursion depth is \(O(m + n - 1)\).
3. **Total Space Complexity**:
   O(m \* n \* 3 + m + n - 1) = O(m \times n)



---


# Code
```python3 []
class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m = len(coins)
        n = len(coins[0])
        cache = {}
        def dfs(i, j, k):
            if i >= m or j >= n:
                return float('-inf')
            if i == m-1 and j == n-1:
                # print(i, j)
                return max(0, coins[i][j]) if coins[i][j] < 0 and k > 0 else coins[i][j]

            if (i, j, k) in cache:
                return cache[(i, j,k)]

            val = coins[i][j]

            d = dfs(i+1, j, k)
            r = dfs(i, j+1, k)

            max_coins = max(d, r) + val

            if val < 0 and k > 0:
                neturalized = max(dfs(i+1, j, k-1), dfs(i, j+1, k-1))
                max_coins = max(max_coins, neturalized)
            cache[(i, j, k)] = max_coins
            # print(i, j, k, max_coins)
            return max_coins
        return dfs(0, 0, 2)
```
['Depth-First Search', 'Memoization', 'Python3']