Maximum amount of money robot can earn

Array Dynamic Programming Matrix

29.5% acceptance

Feb 25, 2026

137

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_amount(coins: Vec<Vec<i32>>) -> i32 {
    let m = coins.len();
    let n = coins[0].len();
    const NEG: i32 = i32::MIN / 2;
    // dp[i][j][k] = max coins at (i,j) with k neutralizations remaining
    let mut dp = vec![vec![[NEG; 3]; n]; m];
    dp[0][0][2] = coins[0][0];
    dp[0][0][1] = 0; // neutralize (0,0)
    // propagate right along row 0
    for j in 1..n {
      for k in 0..3usize {
        let prev = dp[0][j-1][k];
        if prev == NEG { continue; }
        let nk = k;
        let val = prev + coins[0][j];
        if val > dp[0][j][nk] { dp[0][j][nk] = val; }
        if k > 0 {
          let val2 = prev;
          if val2 > dp[0][j][k-1] { dp[0][j][k-1] = val2; }
        }
      }
    }
    // propagate down column 0
    for i in 1..m {
      for k in 0..3usize {
        let prev = dp[i-1][0][k];
        if prev == NEG { continue; }
        let val = prev + coins[i][0];
        if val > dp[i][0][k] { dp[i][0][k] = val; }
        if k > 0 {
          let val2 = prev;
          if val2 > dp[i][0][k-1] { dp[i][0][k-1] = val2; }
        }
      }
    }
    for i in 1..m {
      for j in 1..n {
        for k in 0..3usize {
          for &prev in &[dp[i-1][j][k], dp[i][j-1][k]] {
            if prev == NEG { continue; }
            let val = prev + coins[i][j];
            if val > dp[i][j][k] { dp[i][j][k] = val; }
            if k > 0 {
              let val2 = prev;
              if val2 > dp[i][j][k-1] { dp[i][j][k-1] = val2; }
            }
          }
        }
      }
    }
    *dp[m-1][n-1].iter().max().unwrap()
  }
}