Easy,Small,Well Explained, Beginner Friendly Solution , Recursive (memoization) , Top-down DP 
ApproachThis question was asked during my telephonic interview with Google three years back.(The initial question was similar; however, the interviewer later ad

# Approach

This question was asked during my telephonic interview with **Google** three years back.(The initial question was similar; however, the interviewer later adjusted the problem to make it more complex). That day I solved it via iterative approach, now this time using recursion:

Basic approach to select the value:

- **In case cell with positive value:**  
  - Select the value of the current cell and move to either down or right (↓ →). 
- **In case cell with negative value:** 
  - If **Neutraliztion power is greater than 0:** we have option either use the neutraliztion power and reduce it by 1 (In this case we will add nothing) or don't use the power and let the power value same and select the value of the current cell and move ↓ → .
  - If **Neutraliztion power is 0:** then no option left to select the value of the current cell and move ↓ → (down or right).

Do the max of all these cases and store it.

In general terms for negative value:

```
max(move i+1 with neutraliztion, move j+1 with neutraliztion , grid[i][j]+ move i+1 without neutraliztion, grid[i][j] + move j+1 without neutraliztion) 
```

In general terms for positive value:

```
max(grid[i][j] + move i+1 without neutraliztion, grid[i][j] + move j+1 without neutraliztion) 
```

**USED THE FLAT DP INSTEAD OF 3D DP.**

# Complexity
- Time complexity:$$O(m*n*k)$$
- Space complexity: $$O(m*n*k)$$ - worst case it will never take that much space

# Code
```python3 []
import sys
sys.setrecursionlimit(10**8)
class Solution:
    def dpFunc(self,grid,dp,i,j,neutral):
        if(i>=len(grid) or j>=len(grid[0])):
            return -100000000
        if(i==len(grid)-1 and j==len(grid[0])-1):
            if(neutral > 0 and grid[i][j] < 0):
                return 0
            return grid[i][j]
        if((i,j,neutral) in dp):
            return dp[(i,j,neutral)]
        val = -100000000
        if(grid[i][j]<0 and neutral>0):
            val = max(self.dpFunc(grid,dp,i+1,j,neutral-1),self.dpFunc(grid,dp,i,j+1,neutral-1))
        dp[(i,j,neutral)] = max(grid[i][j]+self.dpFunc(grid,dp,i+1,j,neutral),grid[i][j]+self.dpFunc(grid,dp,i,j+1,neutral),val)
        return dp[(i,j,neutral)]
            
            
            
        
        
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m,n = len(coins), len(coins[0])
        dp = {}
        return(self.dpFunc(coins,dp,0,0,2))



```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python3']