Max Path Sum with small twist | DP | Top Down
This is just standard max path sum problem with a small twist that we can ignore upto k negative cells along the path. everything else remains same.Codeyou can
This is just standard max path sum problem with a small twist that we can ignore upto k negative cells along the path. everything else remains same.

# Code
```cpp []
class Solution {
public:
    
    int dp[500][500][3];
    int done[500][500][3];
 
    int rec(int lx, int ly, int k, vector<vector<int>>&c){
        int n = c.size();
        int m  = c[0].size();
        // pruning 
        if(lx>=n|| ly>=m){
            return -1e9;
        }
        // base case
        if(lx==n-1&& ly==m-1){
            if(c[lx][ly]>=0){
                return c[lx][ly];
            }
            else{
                // if it is not positive
                int notrob = k<2?0:-1e9;
                int rob = c[lx][ly];
                return max(rob,notrob);
            }
        }
        // cache check
        if(done[lx][ly][k]!=-1){
            return dp[lx][ly][k];
        }
        // compute and transition
        // current state = lx,ly ,k
        int right = rec(lx+1,ly,k,c);
        int down = rec(lx,ly+1,k,c);
        int nolifeline = max(right,down)+c[lx][ly];
        int lifeline = -1e9;
        if(c[lx][ly]<0 && k<2){
            int fromleft = rec(lx+1,ly,k+1,c);
            int fromtop = rec(lx,ly+1,k+1,c);
            lifeline = max(fromleft,fromtop);
        }
        dp[lx][ly][k] = max(nolifeline,lifeline);
        done[lx][ly][k] =1;
        return dp[lx][ly][k];
        
        
        // save and return 
    }
    int maximumAmount(vector<vector<int>>& c) {
        // maximum oath sum in grid , either right or down
        // small variation - if current cell is negative , max two times you can avoid adding in the ur total sum
        // return total sum 
        // top down approach 
        int n = c.size();
        int m = c[0].size();
        memset(dp,-1,sizeof(dp));
        memset(done,-1,sizeof(done));
        // return rec(n-1,m-1,2,c);
        return rec(0,0,0,c);
        
    }
};
```
you can find my detailed solution here 
https://youtu.be/7oTFJDGVQPM
['Dynamic Programming', 'Memoization', 'C++']