Dynamic Programming with a 3D Matrix
IntuitionWe will create a matrix, where each cell contains the maximum possible coins which the robot can obtain by starting its jounrney from that cell.Approac
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We will create a matrix, where each cell contains the maximum possible coins which the robot can obtain by starting its jounrney from that cell.

# Approach
<!-- Describe your approach to solving the problem. -->
Each cell has three dimensions:-
1. First (0) - The row of that cell.
2. Second (1) - The column of that cell.
3. Third (2) - Number of remaining neutralizations when arriving at that cell.

We start from the last cell, and calculate the values of all cells in reverse, untill we reach the first cell.

#### The formula I came up with is given below:

![image.png](https://assets.leetcode.com/users/images/3de8ef9c-4219-4d2d-8893-768d6dc939bb_1737144804.3497808.png)

##### Where: i = row, j = column, n = no. of neutralizations left

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

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

# Code
```java []
class Solution {
    public int maximumAmount(int[][] coins) {     
        // Number of rows   
        int m = coins.length;
        // Number of columns
        int n = coins[0].length;

        // 3D Matrix for storing all posible steps
        int[][][] solution = new int[m][n][3];

        // Iteration variables
        int row = 0, col = 0;
        int currentBlock = 0;

        // For -ve current value
        int[] neutralizeRobber = new int[3];   
        int[] dontNeutralizeRobber = new int[3];

        // For +ve current value
        int[] currentBlockMax = new int[3];

        // Booleans for validating whether the robot can
        // move Right or move Down
        boolean canRobotMoveRight = false;
        boolean canRobotMoveDown = false;

        for (int i = 0; i < m; i++) {
            // Iterate each row
            row = m - 1 - i;

            // Calculate posible down movements
            canRobotMoveDown = row + 1 < m;

            for (int j = 0; j < n; j++) {
                // Iterate each column
                col = n - 1 - j;

                // Value of the current block
                currentBlock = coins[row][col];

                // Calculate posible right movements
                canRobotMoveRight = col + 1 < n;

                if (currentBlock < 0) {
                    // If current block is a Robber
                    
                    // Initialize with MIN integer value
                    neutralizeRobber[0] = Integer.MIN_VALUE;
                    neutralizeRobber[1] = Integer.MIN_VALUE;    

                    // Initialize with MIN integer value
                    dontNeutralizeRobber[0] = Integer.MIN_VALUE;
                    dontNeutralizeRobber[1] = Integer.MIN_VALUE;
                    dontNeutralizeRobber[2] = Integer.MIN_VALUE;

                    if (!canRobotMoveRight && !canRobotMoveDown) {
                        // Current block is the last block
                        neutralizeRobber[0] = 0;
                        neutralizeRobber[1] = 0;

                        dontNeutralizeRobber[0] = currentBlock;
                        dontNeutralizeRobber[1] = currentBlock;
                        dontNeutralizeRobber[2] = currentBlock;
                    }             
                    if (canRobotMoveRight) {
                        // Calculate values for possible steps when moving right
                        // and neutralizing the robber
                        neutralizeRobber[0] = solution[row][col + 1][0];
                        neutralizeRobber[1] = max(solution[row][col + 1][0], solution[row][col + 1][1]);

                        // Calculate values for possible steps when moving right
                        // and not neutralizing the robber
                        dontNeutralizeRobber[0] = currentBlock + solution[row][col + 1][0];
                        dontNeutralizeRobber[1] = currentBlock + max(solution[row][col + 1][0], solution[row][col + 1][1]);
                        dontNeutralizeRobber[2] = currentBlock + max(solution[row][col + 1][1], solution[row][col + 1][2]);
                    }
                    if (canRobotMoveDown) {
                        // Calculate values for possible steps when moving down
                        // and neutralizing the robber
                        neutralizeRobber[0] = max(neutralizeRobber[0], solution[row + 1][col][0]);
                        neutralizeRobber[1] = max(neutralizeRobber[1], max(solution[row + 1][col][0], solution[row + 1][col][1]));

                        // Calculate values for possible steps when moving down
                        // and not neutralizing the robber
                        dontNeutralizeRobber[0] = max(dontNeutralizeRobber[0], currentBlock + solution[row + 1][col][0]);
                        dontNeutralizeRobber[1] = max(dontNeutralizeRobber[1], currentBlock + max(solution[row + 1][col][0], solution[row + 1][col][1]));
                        dontNeutralizeRobber[2] = max(dontNeutralizeRobber[2], currentBlock + max(solution[row + 1][col][1], solution[row + 1][col][2]));
                   
                    }     

                    // Calculate the overall solution for the current block
                    // for all posibilities
                    solution[row][col][0] = dontNeutralizeRobber[0];
                    solution[row][col][1] = max(dontNeutralizeRobber[1], neutralizeRobber[0]);
                    solution[row][col][2] = max(dontNeutralizeRobber[2], neutralizeRobber[1]);
                }
                else {
                    // Initialize with MIN integer value
                    currentBlockMax[0] = Integer.MIN_VALUE;
                    currentBlockMax[1] = Integer.MIN_VALUE;
                    currentBlockMax[2] = Integer.MIN_VALUE;
                    
                    if (!canRobotMoveRight && !canRobotMoveDown) {
                        // Current block is the last block
                        currentBlockMax[0] = currentBlock;
                        currentBlockMax[1] = currentBlock;
                        currentBlockMax[2] = currentBlock;
                    }
                    if (canRobotMoveRight) {
                        // Calculate values for possible steps when moving right
                        currentBlockMax[0] = currentBlock + solution[row][col + 1][0];
                        currentBlockMax[1] = currentBlock + solution[row][col + 1][1];
                        currentBlockMax[2] = currentBlock + solution[row][col + 1][2];
                    }
                    if (canRobotMoveDown) {
                        // Calculate values for possible steps when moving down
                        currentBlockMax[0] = max(currentBlockMax[0], currentBlock + solution[row + 1][col][0]);
                        currentBlockMax[1] = max(currentBlockMax[1], currentBlock + solution[row + 1][col][1]);
                        currentBlockMax[2] = max(currentBlockMax[2], currentBlock + solution[row + 1][col][2]);
                    }

                    // Calculate the overall solution for the current block
                    // for all posibilities
                    solution[row][col][0] = currentBlockMax[0];
                    solution[row][col][1] = currentBlockMax[1];
                    solution[row][col][2] = currentBlockMax[2];
                }
            }
        }

        return max(solution[0][0][0], max(solution[0][0][1], solution[0][0][2]));
    }

    public static int max(int firstNumber, int secondNumber) {
        // Return the largest number
        return firstNumber > secondNumber ? firstNumber : secondNumber;
    }
}
```
['Java']