Iterative DP | Tabulation | Clear solution | Python | (Beats 100%)
IntuitionSince the question contains that the cost needs to be calculated by moving right or bottom the hint can be taken that the question needs to be solved u
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Since the question contains that the cost needs to be calculated by moving right or bottom the hint can be taken that the question needs to be solved using Dp.

(Tip: same applies even if they give left and top, if it is all 4 directions then we can use dfs). 

Now coming to dp we also need to decide the dimensions of dp array .If it was just finding the maximum coins without the extra feature of neutralizing, you can directly use a simple 2D dp array as that would be common 2d dp question. Since there is a neutralization thing that we need to do and it has to be done optimally, hence we need to use another dimension in the dp array which decides the number of neutralizations made untill now.

The final answer would be the maximum of 
DP[m-1][n-1][0] , DP[m-1][n-1][1] , DP[m-1][n-1][2]

since maximum of 2 neutralizations can be made.
# Approach
<!-- Describe your approach to solving the problem. -->
To solve any Dp problem no matter how many dimensions it may need,we do the following steps:

1. **Finding if it contains any overlapping subproblem or optimal sub-structure:**

    We already saw the question contains going right and bottom which comes under optimal substructure hence we use dp

2. **Defining the DP state:**

    DP[ i ][ j ][ k ] defines maximum coins required to reach (i,j) from (0,0) by moving either right or bottom only and neutralizing exactly k times along the path.

3. **Drawing state space tree:**

    At every state check how the current state is depending on previous state. In this question the current cell cost depends on above cell and left cell with two cases (neutralize current cell and donot neutralize)

4. **Writing DP expression:**
    from the state space tree we can easily write the dp expression
```
dp[i][j][k]=max(
                    dp[i][j-1][k]+cost[i][j],
                    dp[i][j-1][k-1],
                    dp[i-1][j][k]+cost[i][j],
                    dp[i-1][j][k-1]
                )
```

5. **Base conditions:**
```
    dp[0][0][k]=max(coins[i][j],0)
```
Wherever the expression can go list index out of range we check those using if else and write the code accordingly.
    


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(M*N)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(M*N*3)
# Code
```python3 []
class Solution:
    def maximumAmount(self, cost: List[List[int]]) -> int:
        m=len(cost)
        n=len(cost[0])
        #Initializing DP array
        dp=[]
        for i in range(m):
            l=[]
            for j in range(n):
                y=[0]*3
                l.append(y)
            dp.append(l)
        
        #Constructing the DP array
        for i in range(m):
            for j in range(n):
                for k in range(3):
                    if k==0:
                        if i-1<0 and j-1<0:# Top-left corner of the grid
                            dp[i][j][k]=cost[i][j]
                        elif i-1<0: # First row (no cell above)
                            dp[i][j][k]=dp[i][j-1][k]+cost[i][j]
                        elif j-1<0: # First column (no cell to the left)
                            dp[i][j][k]=dp[i-1][j][k]+cost[i][j]
                        else:  # General case
                            dp[i][j][k]=max(dp[i][j-1][k]+cost[i][j],dp[i-1][j][k]+cost[i][j])
                    else:
                        if i-1<0 and j-1<0:# Top-left corner of the grid
                            dp[i][j][k]=max(cost[i][j],0)
                        elif i-1<0: # First row (no cell above)
                            dp[i][j][k]=max(dp[i][j-1][k]+cost[i][j],dp[i][j-1][k-1])
                        elif j-1<0: # First column (no cell to the left)
                            dp[i][j][k]=max(dp[i-1][j][k]+cost[i][j],dp[i-1][j][k-1])
                        else:  # General case
                            dp[i][j][k]=max(dp[i][j-1][k]+cost[i][j],dp[i-1][j][k]+cost[i][j],dp[i][j-1][k-1],dp[i-1][j][k-1])

                        
        return max(dp[m-1][n-1][0],dp[m-1][n-1][1],dp[m-1][n-1][2])

```
['Dynamic Programming', 'Matrix', 'Python3']