3418
IntuitionTop down intutionApproachRecursion+DPComplexity
Time complexity:
O(mn3);
Space complexity:
O(mn3);Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Top down intution

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

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

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

# Code
```java []
class Solution {
    Integer dp[][][];
    public int dfs(int[][] coins,int i,int j,int move){
        if(i>=coins.length || j>=coins[0].length || move<0){
            return -(int)1e9;
        }
        if(i==coins.length-1 && j==coins[0].length-1){
            int val=coins[i][j]<0?move>0?0:coins[i][j]:coins[i][j];
            return val;
        }
        if(dp[i][j][move]!=null)return dp[i][j][move];

        int val=coins[i][j];
        int right=val+dfs(coins,i,j+1,move);
        int down=val+dfs(coins,i+1,j,move);
        int skip1=dfs(coins,i,j+1,move-1);
        int skip2=dfs(coins,i+1,j,move-1);
        return dp[i][j][move]=Math.max(Math.max(right,down),Math.max(skip1,skip2));
    }
    public int maximumAmount(int[][] coins) {
        dp=new Integer[coins.length][coins[0].length][3];
        return dfs(coins,0,0,2);
    }
}
```
['Java']