Dynammic programming | memoization
IntuitionStandard grid problem.Since maximising profit is asked for. We can think of recursion.BFS is not thought of as shortest or longest path is not asked. H
# Intuition
Standard grid problem.Since maximising profit is asked for. We can think of recursion.BFS is not thought of as shortest or longest path is not asked. Here all possible paths need to be explored.

# Approach
- Go from 0,0 cell to m-1,n-1 cell. Paths only right and down.
- if coins[i][j]>=0 just pick the value normally.
- when <0 just pick value once by subtracting the neutral, other keeping neutral the same and select the maxpath.
- Do same for down path.
- Select max of both paths and return at the end.
- Optimise using 3d dp.


# Complexity
- Time complexity:
O(N*M*2)

- Space complexity:
O(N*M*2)

# Code
```cpp []
class Solution {
public:
    int maxProfit(int row,int col,vector<vector<int>>& coins,int neutral,vector<vector<vector<int>>>&dp){
        int m=coins.size();
        int n=coins[0].size();
        if(row>=m || col>=n)return -1e9;
        if(row==m-1 && col==n-1){
            if(coins[row][col]>=0)return coins[row][col];
            else{
                if(neutral>0){
                    return 0;
                }
                else{
                    return coins[row][col];
                }
            }
        }
        if(dp[row][col][neutral]!=-1)return dp[row][col][neutral];
        //move right
        int right=-1e9;

        if(coins[row][col]>=0)right=coins[row][col] + maxProfit(row,col+1,coins,neutral,dp);
        else {
            if(neutral>0)right=maxProfit(row,col+1,coins,neutral-1,dp);
            right=max(right,maxProfit(row,col+1,coins,neutral,dp)+(coins[row][col]));
        }

        //move down
        int down=-1e9;

        if(coins[row][col]>=0)down=coins[row][col] + maxProfit(row+1,col,coins,neutral,dp);
        else {
            if(neutral>0)down=maxProfit(row+1,col,coins,neutral-1,dp);
            down=max(down,maxProfit(row+1,col,coins,neutral,dp)+(coins[row][col]));
        }
        return dp[row][col][neutral]=max(right,down);
    }
    int maximumAmount(vector<vector<int>>& coins) {
        int m=coins.size();
        int n=coins[0].size();
        vector<vector<vector<int>>>dp(m+1,vector<vector<int>>(n+1,vector<int>(3,-1)));
        return maxProfit(0,0,coins,2,dp);
    }
};
```
['Dynamic Programming', 'Memoization', 'C++']