Maximum Amount of Money Robot Can Earn

Problem

You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time.

The grid contains a value coins[i][j] in each cell:

If coins[i][j] >= 0, the robot gains that many coins.
If coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value of coins[i][j] coins.

The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells.

Note: The robot’s total coins can be negative.

Return the maximum profit the robot can gain on the route.

Example 1

1
2
3
4
5
6
7
8
9


Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output: 8
Explanation:
An optimal path for maximum coins is:
1. Start at `(0, 0)` with `0` coins (total coins = `0`).
2. Move to `(0, 1)`, gaining `1` coin (total coins = `0 + 1 = 1`).
3. Move to `(1, 1)`, where there's a robber stealing `2` coins. The robot uses one neutralization here, avoiding the robbery (total coins = `1`).
4. Move to `(1, 2)`, gaining `3` coins (total coins = `1 + 3 = 4`).
5. Move to `(2, 2)`, gaining `4` coins (total coins = `4 + 4 = 8`).

Example 2

1
2
3
4
5
6
7
8


Input: coins = [[10,10,10],[10,10,10]]
Output: 40
Explanation:
An optimal path for maximum coins is:
1. Start at `(0, 0)` with `10` coins (total coins = `10`).
2. Move to `(0, 1)`, gaining `10` coins (total coins = `10 + 10 = 20`).
3. Move to `(0, 2)`, gaining another `10` coins (total coins = `20 + 10 = 30`).
4. Move to `(1, 2)`, gaining the final `10` coins (total coins = `30 + 10 = 40`).

Constraints

m == coins.length
n == coins[i].length
1 <= m, n <= 500
-1000 <= coins[i][j] <= 1000

Examples

Solution

Method 1 – Dynamic Programming (3D DP for Robber Neutralization)

Intuition

This is a grid DP problem with an extra state: the number of robbers neutralized so far (up to 2). At each cell, the robot can move right or down, and if the cell has a robber, it can choose to neutralize (if it has neutralizations left) or not. We use a 3D DP array to track the best profit at each cell and neutralization count.

Approach

Use a 3D DP array: dp[i][j][k] is the max coins at cell (i, j) with k neutralizations used.
Initialize dp[0][0][0] and, if the start is a robber, also dp[0][0][1].
For each cell, for each possible neutralization count:
- Move right or down, updating the next cell’s DP for both using and not using a neutralization if the cell is a robber.
The answer is the maximum value at the bottom-right cell for any neutralization count (0, 1, or 2).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
public:
    int maximumMoney(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, INT_MIN)));
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) dp[0][0][1] = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    if (dp[i][j][k] == INT_MIN) continue;
                    for (int d = 0; d < 2; ++d) {
                        int ni = i + (d == 0), nj = j + (d == 1);
                        if (ni >= m || nj >= n) continue;
                        int val = coins[ni][nj];
                        // Not neutralize
                        int gain = val >= 0 ? val : val;
                        dp[ni][nj][k] = max(dp[ni][nj][k], dp[i][j][k] + gain);
                        // Neutralize if robber and k < 2
                        if (val < 0 && k < 2)
                            dp[ni][nj][k+1] = max(dp[ni][nj][k+1], dp[i][j][k]);
                    }
                }
            }
        }
        return max({dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2]});
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


func maximumMoney(coins [][]int) int {
    m, n := len(coins), len(coins[0])
    dp := make([][][]int, m)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = []int{math.MinInt32, math.MinInt32, math.MinInt32}
        }
    }
    dp[0][0][0] = coins[0][0]
    if coins[0][0] < 0 {
        dp[0][0][1] = 0
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k <= 2; k++ {
                if dp[i][j][k] == math.MinInt32 {
                    continue
                }
                for d := 0; d < 2; d++ {
                    ni, nj := i, j
                    if d == 0 {
                        ni++
                    } else {
                        nj++
                    }
                    if ni >= m || nj >= n {
                        continue
                    }
                    val := coins[ni][nj]
                    gain := val
                    dp[ni][nj][k] = max(dp[ni][nj][k], dp[i][j][k]+gain)
                    if val < 0 && k < 2 {
                        dp[ni][nj][k+1] = max(dp[ni][nj][k+1], dp[i][j][k])
                    }
                }
            }
        }
    }
    return max3(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])
}
func max(a, b int) int { if a > b { return a }; return b }
func max3(a, b, c int) int { return max(a, max(b, c)) }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int maximumMoney(int[][] coins) {
        int m = coins.length, n = coins[0].length;
        int[][][] dp = new int[m][n][3];
        for (int[][] arr2 : dp)
            for (int[] arr : arr2)
                Arrays.fill(arr, Integer.MIN_VALUE);
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) dp[0][0][1] = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    if (dp[i][j][k] == Integer.MIN_VALUE) continue;
                    for (int d = 0; d < 2; ++d) {
                        int ni = i + (d == 0 ? 1 : 0), nj = j + (d == 1 ? 1 : 0);
                        if (ni >= m || nj >= n) continue;
                        int val = coins[ni][nj];
                        dp[ni][nj][k] = Math.max(dp[ni][nj][k], dp[i][j][k] + val);
                        if (val < 0 && k < 2)
                            dp[ni][nj][k+1] = Math.max(dp[ni][nj][k+1], dp[i][j][k]);
                    }
                }
            }
        }
        return Math.max(dp[m-1][n-1][0], Math.max(dp[m-1][n-1][1], dp[m-1][n-1][2]));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    fun maximumMoney(coins: Array<IntArray>): Int {
        val m = coins.size
        val n = coins[0].size
        val dp = Array(m) { Array(n) { IntArray(3) { Int.MIN_VALUE } } }
        dp[0][0][0] = coins[0][0]
        if (coins[0][0] < 0) dp[0][0][1] = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                for (k in 0..2) {
                    if (dp[i][j][k] == Int.MIN_VALUE) continue
                    for (d in 0..1) {
                        val ni = i + if (d == 0) 1 else 0
                        val nj = j + if (d == 1) 1 else 0
                        if (ni >= m || nj >= n) continue
                        val val_ = coins[ni][nj]
                        dp[ni][nj][k] = maxOf(dp[ni][nj][k], dp[i][j][k] + val_)
                        if (val_ < 0 && k < 2)
                            dp[ni][nj][k+1] = maxOf(dp[ni][nj][k+1], dp[i][j][k])
                    }
                }
            }
        }
        return maxOf(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def maximumMoney(self, coins: list[list[int]]) -> int:
        m, n = len(coins), len(coins[0])
        dp = [[[-float('inf')]*3 for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = coins[0][0]
        if coins[0][0] < 0:
            dp[0][0][1] = 0
        for i in range(m):
            for j in range(n):
                for k in range(3):
                    if dp[i][j][k] == -float('inf'):
                        continue
                    for di, dj in [(1,0),(0,1)]:
                        ni, nj = i+di, j+dj
                        if ni >= m or nj >= n:
                            continue
                        val = coins[ni][nj]
                        dp[ni][nj][k] = max(dp[ni][nj][k], dp[i][j][k] + val)
                        if val < 0 and k < 2:
                            dp[ni][nj][k+1] = max(dp[ni][nj][k+1], dp[i][j][k])
        return max(dp[m-1][n-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn maximum_money(coins: Vec<Vec<i32>>) -> i32 {
        let m = coins.len();
        let n = coins[0].len();
        let mut dp = vec![vec![vec![i32::MIN; 3]; n]; m];
        dp[0][0][0] = coins[0][0];
        if coins[0][0] < 0 { dp[0][0][1] = 0; }
        for i in 0..m {
            for j in 0..n {
                for k in 0..=2 {
                    if dp[i][j][k] == i32::MIN { continue; }
                    for (di, dj) in [(1,0),(0,1)] {
                        let ni = i+di;
                        let nj = j+dj;
                        if ni >= m || nj >= n { continue; }
                        let val = coins[ni][nj];
                        dp[ni][nj][k] = dp[ni][nj][k].max(dp[i][j][k] + val);
                        if val < 0 && k < 2 {
                            dp[ni][nj][k+1] = dp[ni][nj][k+1].max(dp[i][j][k]);
                        }
                    }
                }
            }
        }
        *dp[m-1][n-1].iter().max().unwrap()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    maximumMoney(coins: number[][]): number {
        const m = coins.length, n = coins[0].length;
        const dp = Array.from({length: m}, () => Array.from({length: n}, () => Array(3).fill(-Infinity)));
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) dp[0][0][1] = 0;
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                for (let k = 0; k <= 2; ++k) {
                    if (dp[i][j][k] === -Infinity) continue;
                    for (const [di, dj] of [[1,0],[0,1]]) {
                        const ni = i+di, nj = j+dj;
                        if (ni >= m || nj >= n) continue;
                        const val = coins[ni][nj];
                        dp[ni][nj][k] = Math.max(dp[ni][nj][k], dp[i][j][k] + val);
                        if (val < 0 && k < 2)
                            dp[ni][nj][k+1] = Math.max(dp[ni][nj][k+1], dp[i][j][k]);
                    }
                }
            }
        }
        return Math.max(...dp[m-1][n-1]);
    }
}

Complexity

⏰ Time complexity: O(m * n * 3), since we process each cell and neutralization state.
🧺 Space complexity: O(m * n * 3), for the DP array.

Problem#

Example 1#

Example 2#

Constraints#

Examples#

Solution#

Method 1 – Dynamic Programming (3D DP for Robber Neutralization)#

Intuition#

Approach#

Code#

Complexity#