Memoization from recursion
IntuitionSo we can think that if coins[i][j] >= 0 then pick it up else if its negative then we can choose to use power(if powerCount > 0) else not use power. An
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
So we can think that if coins[i][j] >= 0 then pick it up else if its negative then we can choose to use power(if powerCount > 0) else not use power. And take the maximum answer from right and down. We can use memoization to reduce unecessary calls to things that are getting called again and again.

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

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

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

# Recursion- 
```java[]
class Solution {
    public int maximumAmount(int[][] coins) {
        return getMaximumCoins(0, 0, coins, 2);
    }

    private int getMaximumCoins(int row, int col, int[][] coins, int powerCount) {
        int n = coins.length, m = coins[0].length;

        if(row >= n || col >= m) {
            return Integer.MIN_VALUE;
        } else if(row == n-1 && col == m-1) {
            if(coins[n-1][m-1] >= 0) return coins[n-1][m-1];
            else {
                return powerCount > 0 ? 0 : coins[row][col];
            }
        } else {
            if(coins[row][col] >= 0) {
                int positiveTotal = coins[row][col] + Math.max(getMaximumCoins(row+1, col, coins, powerCount), getMaximumCoins(row, col+1, coins, powerCount));
                return positiveTotal;
            } else {
                int total = Integer.MIN_VALUE;

                if(powerCount > 0) {
                    int negativeTotalWithPowerUse = 0 + Math.max(getMaximumCoins(row+1, col, coins, powerCount-1), getMaximumCoins(row, col+1, coins, powerCount-1));
                    total = Math.max(total, negativeTotalWithPowerUse);
                }

                int negativeTotalWithoutPowerUse = coins[row][col] + 
                    Math.max(
                        getMaximumCoins(row+1, col, coins, powerCount), 
                        getMaximumCoins(row, col+1, coins, powerCount)
                    );

                total = Math.max(total, negativeTotalWithoutPowerUse);
                return total;
            }
        }
    }
}
```

# Code
```java []
class Solution {
    public int maximumAmount(int[][] coins) {
        int n = coins.length, m=coins[0].length;

        int[][][] dp = new int[n][m][3];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                for(int k=0;k<3;k++) {
                    dp[i][j][k] = Integer.MIN_VALUE; 
                }
            }
        }


        return getMaximumCoins(0, 0, coins, 2, dp);
    }

    private int getMaximumCoins(int row, int col, int[][] coins, int powerCount, int[][][] dp) {
        int n = coins.length, m = coins[0].length;

        // Base case if it goes out of bound return Minimum value and not 0(this could give wrong path answer)
        if(row >= n || col >= m) {
            return Integer.MIN_VALUE;
        }
        
        // If we already have the answer then return that no need to calculate
        if(dp[row][col][powerCount] != Integer.MIN_VALUE) {
            return dp[row][col][powerCount];
        } 
        
        // base case if row, col == n-1, m-1 then check the cell value only
        if(row == n-1 && col == m-1) { 
            if(coins[n-1][m-1] >= 0) {
                return dp[n-1][m-1][powerCount] = coins[n-1][m-1];
            }

            return dp[n-1][m-1][powerCount] = (powerCount > 0 ? 0 : coins[row][col]);
        }

        int maxDownWithoutPowerUse = getMaximumCoins(row+1, col, coins, powerCount, dp);
        int maxRightWithoutPowerUse = getMaximumCoins(row, col+1, coins, powerCount, dp);

        if(coins[row][col] >= 0) {
            return dp[row][col][powerCount] = coins[row][col]+Math.max(maxDownWithoutPowerUse, maxRightWithoutPowerUse);
        } else {
            int maxWithoutPowerUse = coins[row][col] + Math.max(maxDownWithoutPowerUse, maxRightWithoutPowerUse);

            int maxWithPowerUse = Integer.MIN_VALUE;
            if(powerCount > 0) {
                int maxDownWithPowerUse = getMaximumCoins(row+1, col, coins, powerCount-1, dp);
                int maxRightWithPowerUse = getMaximumCoins(row, col+1, coins, powerCount-1, dp);
                maxWithPowerUse = Math.max(maxDownWithPowerUse, maxRightWithPowerUse);
            }

            return dp[row][col][powerCount] = Math.max(maxWithoutPowerUse, maxWithPowerUse);
        }
    }
}
```
['Java']