Maximum Amount of Money Robot Can Earn

Intuition #

The problem is a dynamic programming problem with a small twist which is that we can neutralize robbers that rob the robot if the cell is negative at most 2 times.

This will introduce an additional constraint to cell position which is the number of neutralize left to use.

R is len(coins) and C is len(coins[0])-1. nLeft is the number of neutralizations left.

Starting from (0, 0) and going to (R-1, C-1), we at each step consider two cases:

• No neutralizing the robber:
  • We collect coins[y][x] and continue moving down or right.
• Neutralizing the robber (if coins[y][x] < 0):
  • If nLeft > 0 and coins[y][x] < 0, we can neutralize the robber, and “skip” current cell.

We need to consider base cases:

• y and x are out of bounds.
  • If we are out of bounds we cannot return 0 since the result might be negative. We are left with returning math.MinInt ($-\infin$).
• We are at the last cell.
  • If the last cell is negative and we still have left neutralizations we return 0, otherwise we return the last cell’s value.

Can an overflow happen if we return $-\infin$?

The table shows when we return $-\infin$ and the result of the max function used to get the max path value.

Notice that max never has math.MinInt, math.MinInt to result in an integer overflow if we add to it a negative number.

If we do not caught the last cell (bottom right position) an overflow will happen because the table will become:

Approach #

• Let R and C be the number of rows and columns in coins.
• Create a 3D memoization array memo[R][C][3] and initialize all values to negative infinity.
• Define a recursive function dp(y, x, k):
  • Represents the maximum coins collectible starting at cell (y, x) with k skips remaining.
• If (y, x) is out of bounds:
  • Return negative infinity.
• If (y, x) is the bottom-right cell:
  • If k > 0, return max(0, coins[y][x]).
  • Else, return coins[y][x].
• If memo[y][x][k] is already computed:
  • Return the stored value.
• Set current = coins[y][x].
• Compute the value by taking the current cell:
  • take = current + max(dp(y+1, x, k), dp(y, x+1, k))
• Initialize result = take.
• If k > 0 and current < 0:
  • Compute skipping the current cell:
    • skip = max(dp(y+1, x, k-1), dp(y, x+1, k-1))
  • Update result = max(result, skip).
• Store result in memo[y][x][k].
• Return result.
• Call dp(0, 0, 2) and return the result.

Complexity #

• Time complexity: $O(M \times N)$
• Space complexity: $O(M \times N)$
  • We created the memo array to store the state for [][][3]int: $O(3(M \times N)) \rightarrow O(M \times N)$.

Code #

 1import "math"
 2
 3func maximumAmount(coins [][]int) int {
 4	R, C := len(coins), len(coins[0])
 5
 6	memo := make([][][3]int, R)
 7	for y := range R {
 8		memo[y] = make([][3]int, C)
 9		for x := range C {
10			for k := range 3 {
11				memo[y][x][k] = math.MinInt
12			}
13		}
14	}
15
16	var dp func(y, x, nLeft int) int
17	dp = func(y, x, nLeft int) int {
18		if y > len(coins)-1 || x > len(coins[0])-1 {
19			return math.MinInt // Does an overflow might happen? No.
20		}
21
22		// Handling the last cell explicitly to
23		// prevent overflow, because if we
24		// are at the last cell the dp function
25		// will do current+dp(math.MinInt, math.MinInt),
26		// which will result in an integer overflow.
27		if y == len(coins)-1 && x == len(coins[0])-1 {
28			if nLeft > 0 {
29				return max(0, coins[y][x])
30			}
31
32			return coins[y][x]
33		}
34
35		if memo[y][x][nLeft] != math.MinInt {
36			return memo[y][x][nLeft]
37		}
38
39		current := coins[y][x]
40
41		// Having current+ outside of the max function
42		// will prevent integer overflow
43		// for cells out of bounds.
44		v := current + max(dp(y+1, x, nLeft), dp(y, x+1, nLeft))
45
46		if nLeft > 0 && current < 0 {
47			v = max(v, dp(y+1, x, nLeft-1))
48			v = max(v, dp(y, x+1, nLeft-1))
49		}
50
51		memo[y][x][nLeft] = v
52		return v
53	}
54
55	return dp(0, 0, 2)
56}