Maximum Amount of Money Robot Can Earn
Source: leetcode
Difficulty: Medium
Tags: array, dynamic-programming, matrix

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:**



**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.length`
- `n == coins[i].length`
- `1 <= m, n <= 500`
- `-1000 <= coins[i][j] <= 1000`




C++ solution:
class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        const int NEG_INF = -1000000000;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, NEG_INF)));
        if(coins[0][0] >= 0){
            dp[0][0][0] = coins[0][0];
        } else {
            dp[0][0][0] = coins[0][0];
            dp[0][0][1] = 0;
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                for(int used = 0; used < 3; used++){
                    if(dp[i][j][used] == NEG_INF) continue;
                    int current = dp[i][j][used];
                    if(i + 1 < m){
                        int val = coins[i+1][j];
                        if(val >= 0){
                            dp[i+1][j][used] = max(dp[i+1][j][used], current + val);
                        } else {
                            dp[i+1][j][used] = max(dp[i+1][j][used], current + val);
                            if(used < 2){
                                dp[i+1][j][used+1] = max(dp[i+1][j][used+1], current);
                            }
                        }
                    }
                    if(j + 1 < n){
                        int val = coins[i][j+1];
                        if(val >= 0){
                            dp[i][j+1][used] = max(dp[i][j+1][used], current + val);
                        } else {
                            dp[i][j+1][used] = max(dp[i][j+1][used], current + val);
                            if(used < 2){
                                dp[i][j+1][used+1] = max(dp[i][j+1][used+1], current);
                            }
                        }
                    }
                }
            }
        }
        int ans = NEG_INF;
        for (int used = 0; used < 3; used++){
            ans = max(ans, dp[m-1][n-1][used]);
        }
        return ans;
    }
};

Go solution:
func maximumAmount(coins [][]int) int {
	m := len(coins)
	n := len(coins[0])
	negInf := -1 << 55
	dp0 := make([][]int, m)
	dp1 := make([][]int, m)
	dp2 := make([][]int, m)
	for i := 0; i < m; i++ {
		dp0[i] = make([]int, n)
		dp1[i] = make([]int, n)
		dp2[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dp0[i][j] = negInf
			dp1[i][j] = negInf
			dp2[i][j] = negInf
		}
	}
	if coins[0][0] >= 0 {
		dp0[0][0] = coins[0][0]
	} else {
		dp0[0][0] = coins[0][0]
		dp1[0][0] = 0
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				continue
			}
			cand0, cand1, cand2 := negInf, negInf, negInf
			if i > 0 {
				if dp0[i-1][j] > cand0 {
					cand0 = dp0[i-1][j]
				}
				if dp1[i-1][j] > cand1 {
					cand1 = dp1[i-1][j]
				}
				if dp2[i-1][j] > cand2 {
					cand2 = dp2[i-1][j]
				}
			}
			if j > 0 {
				if dp0[i][j-1] > cand0 {
					cand0 = dp0[i][j-1]
				}
				if dp1[i][j-1] > cand1 {
					cand1 = dp1[i][j-1]
				}
				if dp2[i][j-1] > cand2 {
					cand2 = dp2[i][j-1]
				}
			}
			if coins[i][j] >= 0 {
				dp0[i][j] = cand0 + coins[i][j]
				dp1[i][j] = cand1 + coins[i][j]
				dp2[i][j] = cand2 + coins[i][j]
			} else {
				dp0[i][j] = cand0 + coins[i][j]
				a := cand1 + coins[i][j]
				b := cand0
				if a < b {
					dp1[i][j] = b
				} else {
					dp1[i][j] = a
				}
				a = cand2 + coins[i][j]
				b = cand1
				if a < b {
					dp2[i][j] = b
				} else {
					dp2[i][j] = a
				}
			}
		}
	}
	res := dp0[m-1][n-1]
	if dp1[m-1][n-1] > res {
		res = dp1[m-1][n-1]
	}
	if dp2[m-1][n-1] > res {
		res = dp2[m-1][n-1]
	}
	return res
}

Java solution:
class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length, n = coins[0].length;
        int INF = Integer.MIN_VALUE;
        int[][][] dp = new int[m][n][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = INF;
                dp[i][j][1] = INF;
                dp[i][j][2] = INF;
            }
        }
        if (coins[0][0] >= 0) {
            dp[0][0][0] = coins[0][0];
        } else {
            dp[0][0][0] = coins[0][0];
            dp[0][0][1] = 0;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int used = 0; used < 3; used++) {
                    if (dp[i][j][used] == INF)
                        continue;
                    if (j + 1 < n) {
                        int coinVal = coins[i][j + 1];
                        if (coinVal >= 0) {
                            int newVal = dp[i][j][used] + coinVal;
                            dp[i][j + 1][used] = Math.max(dp[i][j + 1][used], newVal);
                        } else {
                            int newVal = dp[i][j][used] + coinVal;
                            dp[i][j + 1][used] = Math.max(dp[i][j + 1][used], newVal);
                            if (used < 2) {
                                newVal = dp[i][j][used];
                                dp[i][j + 1][used + 1] = Math.max(dp[i][j + 1][used + 1], newVal);
                            }
                        }
                    }
                    if (i + 1 < m) {
                        int coinVal = coins[i + 1][j];
                        if (coinVal >= 0) {
                            int newVal = dp[i][j][used] + coinVal;
                            dp[i + 1][j][used] = Math.max(dp[i + 1][j][used], newVal);
                        } else {
                            int newVal = dp[i][j][used] + coinVal;
                            dp[i + 1][j][used] = Math.max(dp[i + 1][j][used], newVal);
                            if (used < 2) {
                                newVal = dp[i][j][used];
                                dp[i + 1][j][used + 1] = Math.max(dp[i + 1][j][used + 1], newVal);
                            }
                        }
                    }
                }
            }
        }
        int ans = INF;
        for (int used = 0; used < 3; used++) {
            ans = Math.max(ans, dp[m - 1][n - 1][used]);
        }
        return ans;
    }
}

JavaScript solution:
var maximumAmount = function(coins) {
    const m = coins.length, n = coins[0].length;
    const dp0 = Array.from({length: m}, () => Array(n).fill(Number.NEGATIVE_INFINITY));
    const dp1 = Array.from({length: m}, () => Array(n).fill(Number.NEGATIVE_INFINITY));
    const dp2 = Array.from({length: m}, () => Array(n).fill(Number.NEGATIVE_INFINITY));
    
    let startVal = coins[0][0];
    if(startVal >= 0) {
        dp0[0][0] = startVal;
    } else {
        dp0[0][0] = startVal;
        dp1[0][0] = 0;
    }
    
    const dirs = [[0,1],[1,0]];
    for (let i = 0; i < m; i++){
        for (let j = 0; j < n; j++){
            if(dp0[i][j] !== Number.NEGATIVE_INFINITY){
                for(let d = 0; d < dirs.length; d++){
                    const ni = i + dirs[d][0], nj = j + dirs[d][1];
                    if (ni < m && nj < n) {
                        let cellVal = coins[ni][nj];
                        let candidate = dp0[i][j] + cellVal;
                        dp0[ni][nj] = Math.max(dp0[ni][nj], candidate);
                        if(cellVal < 0){
                            let candidateNeutral = dp0[i][j] + 0;
                            dp1[ni][nj] = Math.max(dp1[ni][nj], candidateNeutral);
                        }
                    }
                }
            }
            if(dp1[i][j] !== Number.NEGATIVE_INFINITY){
                for(let d = 0; d < dirs.length; d++){
                    const ni = i + dirs[d][0], nj = j + dirs[d][1];
                    if (ni < m && nj < n) {
                        let cellVal = coins[ni][nj];
                        let candidate = dp1[i][j] + cellVal;
                        dp1[ni][nj] = Math.max(dp1[ni][nj], candidate);
                        if(cellVal < 0){
                            let candidateNeutral = dp1[i][j] + 0;
                            dp2[ni][nj] = Math.max(dp2[ni][nj], candidateNeutral);
                        }
                    }
                }
            }
            if(dp2[i][j] !== Number.NEGATIVE_INFINITY){
                for(let d = 0; d < dirs.length; d++){
                    const ni = i + dirs[d][0], nj = j + dirs[d][1];
                    if (ni < m && nj < n) {
                        let cellVal = coins[ni][nj];
                        let candidate = dp2[i][j] + cellVal;
                        dp2[ni][nj] = Math.max(dp2[ni][nj], candidate);
                    }
                }
            }
        }
    }
    
    return Math.max(dp0[m-1][n-1], dp1[m-1][n-1], dp2[m-1][n-1]);
};

Python solution:
class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        NEG_INF = -10**9
        dp = [[[NEG_INF] * 3 for _ in range(n)] for _ in range(m)]
        if coins[0][0] >= 0:
            dp[0][0][0] = coins[0][0]
        else:
            dp[0][0][0] = coins[0][0]
            dp[0][0][1] = 0
        for i in range(m):
            for j in range(n):
                for used in range(3):
                    if dp[i][j][used] == NEG_INF:
                        continue
                    curr = dp[i][j][used]
                    if i + 1 < m:
                        v = coins[i + 1][j]
                        if v >= 0:
                            if curr + v > dp[i + 1][j][used]:
                                dp[i + 1][j][used] = curr + v
                        else:
                            if curr + v > dp[i + 1][j][used]:
                                dp[i + 1][j][used] = curr + v
                            if used < 2 and curr > dp[i + 1][j][used + 1]:
                                dp[i + 1][j][used + 1] = curr
                    if j + 1 < n:
                        v = coins[i][j + 1]
                        if v >= 0:
                            if curr + v > dp[i][j + 1][used]:
                                dp[i][j + 1][used] = curr + v
                        else:
                            if curr + v > dp[i][j + 1][used]:
                                dp[i][j + 1][used] = curr + v
                            if used < 2 and curr > dp[i][j + 1][used + 1]:
                                dp[i][j + 1][used + 1] = curr
        return max(dp[m - 1][n - 1])

Ruby solution:
def maximum_amount(coins)
  m = coins.size
  n = coins[0].size
  neg_inf = -1000000000
  dp = Array.new(m) { Array.new(n) { Array.new(3, neg_inf) } }
  if coins[0][0] >= 0
    dp[0][0][0] = coins[0][0]
  else
    dp[0][0][0] = coins[0][0]
    dp[0][0][1] = 0
  end
  for i in 0...m
    for j in 0...n
      for used in 0..2
        current = dp[i][j][used]
        next if current == neg_inf
        if j + 1 < n
          val = coins[i][j+1]
          if val >= 0
            dp[i][j+1][used] = [dp[i][j+1][used], current + val].max
          else
            dp[i][j+1][used] = [dp[i][j+1][used], current + val].max
            if used < 2
              dp[i][j+1][used+1] = [dp[i][j+1][used+1], current].max
            end
          end
        end
        if i + 1 < m
          val = coins[i+1][j]
          if val >= 0
            dp[i+1][j][used] = [dp[i+1][j][used], current + val].max
          else
            dp[i+1][j][used] = [dp[i+1][j][used], current + val].max
            if used < 2
              dp[i+1][j][used+1] = [dp[i+1][j][used+1], current].max
            end
          end
        end
      end
    end
  end
  dp[m-1][n-1].max
end