Maximum Amount of Money Robot Can Earn
MediumUpdated: Aug 2, 2025
Practice on:
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 ofcoins[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.
Examples
Example 1
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
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.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000
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)withkneutralizations used. - Initialize
dp[0][0][0]and, if the start is a robber, alsodp[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
C++
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]});
}
};
Go
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)) }
Java
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]));
}
}
Kotlin
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])
}
}
Python
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])
Rust
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()
}
}
TypeScript
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.