Easy 3 d dp solution
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int dp[501][501][3];
    int maximumAmount(vector<vector<int>>& coins) {
        int n = coins.size();
        int m = coins[0].size();
        for (int i = 0; i < 501; ++i)
            for (int j = 0; j < 501; ++j)
                for (int k = 0; k < 3; ++k)
                    dp[i][j][k] = INT_MIN;
        for(int k = 0; k < 3; k++){
            for(int i = n - 1; i >= 0; i--){
                for(int j = m - 1; j >= 0; j--){
                    if( i == n-1 && j == m-1){
                        if(k > 0){
                            dp[i][j][k] = max(0, coins[i][j]);
                        }
                        else{
                            dp[i][j][k] = coins[i][j];
                        }
                        continue;
                    }
                    if(coins[i][j] >= 0){
                        int right = j + 1 < m ? dp[i][j + 1][k] : INT_MIN;
                        int down = i + 1 < n ? dp[i + 1][j][k] : INT_MIN;

                        dp[i][j][k] = coins[i][j] + max(right, down);
                    }else{
                        //take
                        int tright = INT_MIN;
                        int tdown = INT_MIN;
                        int take = INT_MIN;
                        if(k > 0){
                            tright = j + 1 < m ? dp[i][j + 1][k - 1] : INT_MIN;
                            tdown = i + 1 < n ? dp[i + 1][j][k - 1] : INT_MIN;
                            take = max(tright, tdown);
                        }

                        int nright = j + 1 < m ? dp[i][j + 1][k] : INT_MIN;
                        int ndown = i + 1 < n ? dp[i + 1][j][k] : INT_MIN;
                        int ntake = coins[i][j] + max(nright, ndown);

                        dp[i][j][k] = max(take, ntake);
                    }

                }
            }
        }
        return dp[0][0][2];
    }
};
```
['C++']