Maximum Amount of Money Robot Can Earn
MedPrompt
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.
Example 1:
Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output: 8
Explanation:
An optimal path for maximum coins is:
- Start at
(0, 0)with0coins (total coins =0). - Move to
(0, 1), gaining1coin (total coins =0 + 1 = 1). - Move to
(1, 1), where there's a robber stealing2coins. The robot uses one neutralization here, avoiding the robbery (total coins =1). - Move to
(1, 2), gaining3coins (total coins =1 + 3 = 4). - Move to
(2, 2), gaining4coins (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:
- Start at
(0, 0)with10coins (total coins =10). - Move to
(0, 1), gaining10coins (total coins =10 + 10 = 20). - Move to
(0, 2), gaining another10coins (total coins =20 + 10 = 30). - Move to
(1, 2), gaining the final10coins (total coins =30 + 10 = 40).
Constraints:
m == coins.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This problem can be solved using dynamic programming. Since the robot's decisions depend on its current position and the number of neutralizations used, we can define a state by (row, column, neutralizations_used). A 3D DP table can store the optimal results for each state.
Algorithm
- Create a 3D DP table
dp[i][j][k]to store the maximum coins to reach cell(i, j)using exactlykneutralizations. - Initialize the
dptable with a very small number to represent unreachable states. - Set the base case for the starting cell
(0, 0). Ifcoins[0][0]is positive,dp[0][0][0] = coins[0][0]. If it's negative,dp[0][0][0] = coins[0][0](no neutralization) anddp[0][0][1] = 0(one neutralization). - Iterate through the grid from
(0, 0)to(m-1, n-1). - For each cell
(i, j)and for each neutralization countk(from 0 to 2), calculatedp[i][j][k]based on the values from the top celldp[i-1][j]and the left celldp[i][j-1]. - If
coins[i][j]is non-negative, the value ismax(from_top, from_left) + coins[i][j]using the samek. - If
coins[i][j]is negative (a robber), there are two choices:- Don't neutralize:
max(from_top, from_left)_k + coins[i][j]. - Neutralize (if
k > 0):max(from_top, from_left)_{k-1}.
- Don't neutralize:
- The value
dp[i][j][k]is the maximum of the valid choices. - The final answer is the maximum value among
dp[m-1][n-1][0],dp[m-1][n-1][1], anddp[m-1][n-1][2].
Walkthrough
We define a 3D DP array, dp[i][j][k], which stores the maximum amount of money the robot can have when it reaches cell (i, j) having used exactly k neutralizations on its path. The third dimension k will have a size of 3, for 0, 1, or 2 neutralizations.
The state transition works as follows: to compute the value for dp[i][j][k], we look at the maximum possible scores from the cells the robot could have come from, which are (i-1, j) (from top) and (i, j-1) (from left).
Let max_prev(k) be max(dp[i-1][j][k], dp[i][j-1][k]).
-
If
coins[i][j] >= 0: The robot collects the coins. The number of neutralizations used does not change. So,dp[i][j][k] = max_prev(k) + coins[i][j]. -
If
coins[i][j] < 0: The robot encounters a robber and has two choices:- Don't neutralize: The robot loses coins. The total coins would be
max_prev(k) + coins[i][j]. - Neutralize: This is possible only if
k > 0. The robot uses one neutralization charge at(i, j). The cost of this cell becomes 0. The state must have transitioned from a path that had usedk-1neutralizations. So, the total coins would bemax_prev(k-1).
- Don't neutralize: The robot loses coins. The total coins would be
dp[i][j][k] is the maximum of these two options. After filling the entire dp table, the maximum profit at the destination (m-1, n-1) is the maximum value across all possible neutralization counts, i.e., max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2]).
class Solution { public long maxAmountOfMoney(int[][] coins) { int m = coins.length; int n = coins[0].length; long[][][] dp = new long[m][n][3]; long UNREACHABLE = Long.MIN_VALUE / 2; // Use a very small number for unreachable states for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < 3; k++) { dp[i][j][k] = UNREACHABLE; } } } // Base case: starting cell (0, 0) if (coins[0][0] >= 0) { dp[0][0][0] = coins[0][0]; } else { // Robber at start dp[0][0][0] = coins[0][0]; // Don't neutralize dp[0][0][1] = 0; // Neutralize } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) continue; for (int k = 0; k < 3; k++) { long maxPrevSameK = UNREACHABLE; if (i > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i - 1][j][k]); if (j > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i][j - 1][k]); long maxPrevMinusOneK = UNREACHABLE; if (k > 0) { if (i > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i - 1][j][k - 1]); if (j > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i][j - 1][k - 1]); } if (coins[i][j] >= 0) { if (maxPrevSameK != UNREACHABLE) { dp[i][j][k] = maxPrevSameK + coins[i][j]; } } else { // Robber at (i, j) long option1 = (maxPrevSameK != UNREACHABLE) ? maxPrevSameK + coins[i][j] : UNREACHABLE; long option2 = (maxPrevMinusOneK != UNREACHABLE) ? maxPrevMinusOneK : UNREACHABLE; if (option1 != UNREACHABLE || option2 != UNREACHABLE) { dp[i][j][k] = Math.max(option1, option2); } } } } } long result = UNREACHABLE; for (int k = 0; k < 3; k++) { result = Math.max(result, dp[m - 1][n - 1][k]); } return result; }}Complexity
Time
O(m * n), as we iterate through each cell of the grid and perform a constant number of operations (for k=0, 1, 2).
Space
O(m * n), for the 3D DP table of size m x n x 3.
Trade-offs
Pros
It's a standard and clear application of dynamic programming.
Guaranteed to find the optimal solution.
Efficient enough for the given problem constraints.
Cons
Uses O(m * n) space, which might be substantial for very large grids, although it fits within the memory limits for the given constraints.
Solutions
Solution
class Solution {private Integer[][][] f;private int[][] coins;private int m;private int n;public int maximumAmount(int[][] coins) { m = coins.length; n = coins[0].length; this.coins = coins; f = new Integer[m][n][3]; return dfs(0, 0, 2); }private int dfs(int i, int j, int k) { if (i >= m || j >= n) { return Integer.MIN_VALUE / 2; } if (f[i][j][k] != null) { return f[i][j][k]; } if (i == m - 1 && j == n - 1) { return k > 0 ? Math.max(0, coins[i][j]) : coins[i][j]; } int ans = coins[i][j] + Math.max(dfs(i + 1, j, k), dfs(i, j + 1, k)); if (coins[i][j] < 0 && k > 0) { ans = Math.max(ans, Math.max(dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1))); } return f[i][j][k] = ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.