DP on Grid (3D) | Recursive | Memoization | Tabulation | Clean and Concise
CodeEdit : My python solution was AC at first but later turned TLE for using -1. So i changed it to inf
# Code
```python3 []
class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m=len(coins)
        n=len(coins[0])
        inf=float('inf')
        dp=[[[inf]*3 for _ in range(n)]for _ in range(m)]

        def solve(i,j,k):
            if i>=m or j>=n or k<0:return -inf
            if i==m-1 and j==n-1:
                if coins[i][j]<0 and k>0:dp[i][j][k]=0
                else: dp[i][j][k]=coins[i][j]
                return dp[i][j][k]
            if dp[i][j][k]!=inf:return dp[i][j][k]
            ans=coins[i][j]+max(solve(i+1,j,k),solve(i,j+1,k))
            if coins[i][j]<0:
                ans=max(ans,max(solve(i+1,j,k-1),solve(i,j+1,k-1)))
            dp[i][j][k]=ans
            return dp[i][j][k]

        return solve(0,0,2)
```
```cpp []
class Solution {
public:
    const int inf=1e9;
    int m,n;
    vector<vector<int>>vec;
    // int dp[501][501][3]={inf};
    
    // bottom up (recursion and memoisation)
    // // using array for memoisation
    // int solve(int i,int j,int k){
    //     if(i>=m||j>=n||k<0)return -inf;
    //     if(i==m-1&&j==n-1)return dp[i][j][k]=(vec[i][j]<0&&k>0)?0:vec[i][j];
    //     if(dp[i][j][k]!=inf)return dp[i][j][k];
    //     int ans=vec[i][j]+max(solve(i+1,j,k),solve(i,j+1,k));
    //     if(vec[i][j]<0)ans=max(ans,max(solve(i+1,j,k-1),solve(i,j+1,k-1)));
    //     return dp[i][j][k]=ans;
    // };
    // // using vector for memoisation
    // int solve(int i,int j,int k,vector<vector<vector<int>>>&dp){
    //     if(i>=m||j>=n||k<0)return -inf;
    //     if(i==m-1&&j==n-1)return dp[i][j][k]=(vec[i][j]<0&&k>0)?0:vec[i][j];
    //     if(dp[i][j][k]!=inf)return dp[i][j][k];
    //     int ans=vec[i][j]+max(solve(i+1,j,k,dp),solve(i,j+1,k,dp));
    //     if(vec[i][j]<0)ans=max(ans,max(solve(i+1,j,k-1,dp),solve(i,j+1,k-1,dp)));
    //     return dp[i][j][k]=ans;
    // };

    int maximumAmount(vector<vector<int>>& coins) {
        m=coins.size();n=coins[0].size();vec=coins;
        vector<vector<vector<int>>>dp(m+1,vector<vector<int>>(n+1,vector<int>(3,-inf)));
        // vector<vector<vector<int>>>dp(m+1,vector<vector<int>>(n+1,vector<int>(3,inf)));
        // for(int i=0;i<m;++i)for(int j=0;j<n;++j)for(int k=0;k<3;++k)dp[i][j][k]=inf;
        // return solve(0,0,2);

        // top down (tabulation)
        for(int i=m-1;i>=0;--i){
            for(int j=n-1;j>=0;--j){
                for(int k=0;k<3;++k){
                    if(i==m-1&&j==n-1){dp[i][j][k]=(coins[i][j]<0&&k>0)?0:coins[i][j];continue;}
                    int ans=coins[i][j]+max(dp[i+1][j][k],dp[i][j+1][k]);
                    if(coins[i][j]<0&&k>0)ans=max(ans,max(dp[i+1][j][k-1],dp[i][j+1][k-1]));
                    dp[i][j][k]=ans;
                }
            }
        }
        return dp[0][0][2];
    }
};
```

Edit : My python solution was AC at first but later turned TLE for using `-1`. So i changed it to `inf`

['Dynamic Programming', 'Recursion', 'Memoization', 'C++', 'Python3']