Maximum Amount of Money Robot Can Earn

Med

#3037Time: 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.1 company

Patterns

Dynamic Programming

Data structures

Array Matrix

Companies

PhonePe

Prompt

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:

Start at (0, 0) with 0 coins (total coins = 0).
Move to (0, 1), gaining 1 coin (total coins = 0 + 1 = 1).
Move to (1, 1), where there's a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1).
Move to (1, 2), gaining 3 coins (total coins = 1 + 3 = 4).
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:

Start at (0, 0) with 10 coins (total coins = 10).
Move to (0, 1), gaining 10 coins (total coins = 10 + 10 = 20).
Move to (0, 2), gaining another 10 coins (total coins = 20 + 10 = 30).
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

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 exactly k neutralizations.
Initialize the dp table with a very small number to represent unreachable states.
Set the base case for the starting cell (0, 0). If coins[0][0] is positive, dp[0][0][0] = coins[0][0]. If it's negative, dp[0][0][0] = coins[0][0] (no neutralization) and dp[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 count k (from 0 to 2), calculate dp[i][j][k] based on the values from the top cell dp[i-1][j] and the left cell dp[i][j-1].
If coins[i][j] is non-negative, the value is max(from_top, from_left) + coins[i][j] using the same k.
If coins[i][j] is negative (a robber), there are two choices:
1. Don't neutralize: max(from_top, from_left)_k + coins[i][j].
2. Neutralize (if k > 0): max(from_top, from_left)_{k-1}.
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], and dp[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:
1. Don't neutralize: The robot loses coins. The total coins would be max_prev(k) + coins[i][j].
2. 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 used k-1 neutralizations. So, the total coins would be max_prev(k-1).

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]).

1class Solution {2    public long maxAmountOfMoney(int[][] coins) {3        int m = coins.length;4        int n = coins[0].length;5        long[][][] dp = new long[m][n][3];6        long UNREACHABLE = Long.MIN_VALUE / 2; // Use a very small number for unreachable states7 8        for (int i = 0; i < m; i++) {9            for (int j = 0; j < n; j++) {10                for (int k = 0; k < 3; k++) {11                    dp[i][j][k] = UNREACHABLE;12                }13            }14        }15 16        // Base case: starting cell (0, 0)17        if (coins[0][0] >= 0) {18            dp[0][0][0] = coins[0][0];19        } else { // Robber at start20            dp[0][0][0] = coins[0][0]; // Don't neutralize21            dp[0][0][1] = 0;           // Neutralize22        }23 24        for (int i = 0; i < m; i++) {25            for (int j = 0; j < n; j++) {26                if (i == 0 && j == 0) continue;27 28                for (int k = 0; k < 3; k++) {29                    long maxPrevSameK = UNREACHABLE;30                    if (i > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i - 1][j][k]);31                    if (j > 0) maxPrevSameK = Math.max(maxPrevSameK, dp[i][j - 1][k]);32 33                    long maxPrevMinusOneK = UNREACHABLE;34                    if (k > 0) {35                        if (i > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i - 1][j][k - 1]);36                        if (j > 0) maxPrevMinusOneK = Math.max(maxPrevMinusOneK, dp[i][j - 1][k - 1]);37                    }38 39                    if (coins[i][j] >= 0) {40                        if (maxPrevSameK != UNREACHABLE) {41                            dp[i][j][k] = maxPrevSameK + coins[i][j];42                        }43                    } else { // Robber at (i, j)44                        long option1 = (maxPrevSameK != UNREACHABLE) ? maxPrevSameK + coins[i][j] : UNREACHABLE;45                        long option2 = (maxPrevMinusOneK != UNREACHABLE) ? maxPrevMinusOneK : UNREACHABLE;46                        47                        if (option1 != UNREACHABLE || option2 != UNREACHABLE) {48                            dp[i][j][k] = Math.max(option1, option2);49                        }50                    }51                }52            }53        }54 55        long result = UNREACHABLE;56        for (int k = 0; k < 3; k++) {57            result = Math.max(result, dp[m - 1][n - 1][k]);58        }59        60        return result;61    }62}

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.

This approach optimizes the space complexity of the standard DP solution. By observing that the calculation for the current row only depends on the previous row, we can avoid storing the entire m x n grid. We only need to keep track of two rows at a time, significantly reducing memory usage.

Algorithm

Observe that computing the DP values for row i only requires the values from row i-1.
Use two 2D arrays, prevDp and currDp, both of size n x 3, to store DP values for the previous and current rows, respectively.
Initialize prevDp by computing the results for the first row (i=0) of the grid.
Iterate from the second row (i=1) to the last row (m-1).
In each iteration i, compute currDp based on prevDp (for values from the top cell) and currDp itself (for values from the left cell).
After computing the entire currDp for row i, swap the roles of the arrays: prevDp becomes currDp for the next iteration.
The final answer is the maximum value in the last row of the prevDp table, i.e., max(prevDp[n-1][0], prevDp[n-1][1], prevDp[n-1][2]).

Walkthrough

The O(m * n) space complexity of the previous approach can be optimized. When we compute the DP values for row i, we only need access to the values from row i-1 and the values already computed in the current row i. This suggests that we don't need to store the entire DP table in memory.

We can use two arrays, say prevDp and currDp, each of size n x 3. prevDp will hold the DP values for the previous row (i-1), and currDp will be used to calculate the values for the current row (i).

The process is as follows:

First, we compute the DP values for the entire first row (i=0) and store them in prevDp.
Then, we iterate from i = 1 to m-1. In each iteration, we compute currDp for row i.
To calculate currDp[j][k], we use prevDp[j][k] (value from the cell above) and currDp[j-1][k] (value from the cell to the left).
After row i is fully computed in currDp, we no longer need the old prevDp. So, we set prevDp = currDp and prepare a new currDp for the next row.
This process continues until we have computed the values for the last row.

The final result is the maximum value in the prevDp array for the last column, n-1.

1class Solution {2    public long maxAmountOfMoney(int[][] coins) {3        int m = coins.length;4        int n = coins[0].length;5        long UNREACHABLE = Long.MIN_VALUE / 2;6 7        long[][] prevDp = new long[n][3];8 9        for (int j = 0; j < n; j++) {10            for (int k = 0; k < 3; k++) {11                prevDp[j][k] = UNREACHABLE;12            }13        }14 15        // Initialize for the first row (i=0)16        if (coins[0][0] >= 0) {17            prevDp[0][0] = coins[0][0];18        } else {19            prevDp[0][0] = coins[0][0];20            prevDp[0][1] = 0;21        }22 23        for (int j = 1; j < n; j++) {24            for (int k = 0; k < 3; k++) {25                long fromLeftSameK = prevDp[j - 1][k];26                long fromLeftMinusOneK = (k > 0) ? prevDp[j - 1][k - 1] : UNREACHABLE;27                28                if (coins[0][j] >= 0) {29                    if (fromLeftSameK != UNREACHABLE) prevDp[j][k] = fromLeftSameK + coins[0][j];30                } else {31                    long opt1 = (fromLeftSameK != UNREACHABLE) ? fromLeftSameK + coins[0][j] : UNREACHABLE;32                    long opt2 = fromLeftMinusOneK;33                    if (opt1 != UNREACHABLE || opt2 != UNREACHABLE) prevDp[j][k] = Math.max(opt1, opt2);34                }35            }36        }37 38        // Iterate through the rest of the rows39        for (int i = 1; i < m; i++) {40            long[][] currDp = new long[n][3];41            for (int j = 0; j < n; j++) for (int k = 0; k < 3; k++) currDp[j][k] = UNREACHABLE;42 43            for (int j = 0; j < n; j++) {44                for (int k = 0; k < 3; k++) {45                    long fromTopSameK = prevDp[j][k];46                    long fromLeftSameK = (j > 0) ? currDp[j - 1][k] : UNREACHABLE;47                    long maxPrevSameK = Math.max(fromTopSameK, fromLeftSameK);48                    if (fromTopSameK == UNREACHABLE) maxPrevSameK = fromLeftSameK;49                    if (fromLeftSameK == UNREACHABLE) maxPrevSameK = fromTopSameK;50 51                    long fromTopMinusOneK = (k > 0) ? prevDp[j][k - 1] : UNREACHABLE;52                    long fromLeftMinusOneK = (k > 0 && j > 0) ? currDp[j - 1][k - 1] : UNREACHABLE;53                    long maxPrevMinusOneK = Math.max(fromTopMinusOneK, fromLeftMinusOneK);54                    if (fromTopMinusOneK == UNREACHABLE) maxPrevMinusOneK = fromLeftMinusOneK;55                    if (fromLeftMinusOneK == UNREACHABLE) maxPrevMinusOneK = fromTopMinusOneK;56 57                    if (coins[i][j] >= 0) {58                        if (maxPrevSameK != UNREACHABLE) currDp[j][k] = maxPrevSameK + coins[i][j];59                    } else { // Robber60                        long opt1 = (maxPrevSameK != UNREACHABLE) ? maxPrevSameK + coins[i][j] : UNREACHABLE;61                        long opt2 = maxPrevMinusOneK;62                        if (opt1 != UNREACHABLE || opt2 != UNREACHABLE) currDp[j][k] = Math.max(opt1, opt2);63                    }64                }65            }66            prevDp = currDp;67        }68 69        long result = UNREACHABLE;70        for (int k = 0; k < 3; k++) {71            result = Math.max(result, prevDp[n - 1][k]);72        }73        return result;74    }75}

Complexity

Time

O(m * n), same as the previous approach.

Space

O(n), as we only need to store two rows of size n x 3.

Trade-offs

Pros

Highly memory-efficient, making it suitable for problems with very large row counts.
Maintains the same optimal time complexity as the unoptimized version.

Cons

The implementation can be slightly more complex due to managing two arrays and handling the first row/column as special cases.

Solutions

Solution

1class Solution {2private3  Integer[][][] f;4private5  int[][] coins;6private7  int m;8private9  int n;10public11  int maximumAmount(int[][] coins) {12    m = coins.length;13    n = coins[0].length;14    this.coins = coins;15    f = new Integer[m][n][3];16    return dfs(0, 0, 2);17  }18private19  int dfs(int i, int j, int k) {20    if (i >= m || j >= n) {21      return Integer.MIN_VALUE / 2;22    }23    if (f[i][j][k] != null) {24      return f[i][j][k];25    }26    if (i == m - 1 && j == n - 1) {27      return k > 0 ? Math.max(0, coins[i][j]) : coins[i][j];28    }29    int ans = coins[i][j] + Math.max(dfs(i + 1, j, k), dfs(i, j + 1, k));30    if (coins[i][j] < 0 && k > 0) {31      ans = Math.max(ans, Math.max(dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)));32    }33    return f[i][j][k] = ans;34  }35}

1class Solution {2public:3  int maximumAmount(vector<vector<int>> &coins) {4    int m = coins.size(), n = coins[0].size();5    vector<vector<vector<int>>> f(m,6                                  vector<vector<int>>(n, vector<int>(3, -1)));7    auto dfs = [&](this auto &&dfs, int i, int j, int k) -> int {8      if (i >= m || j >= n) {9        return INT_MIN / 2;10      }11      if (f[i][j][k] != -1) {12        return f[i][j][k];13      }14      if (i == m - 1 && j == n - 1) {15        return k > 0 ? max(0, coins[i][j]) : coins[i][j];16      }17      int ans = coins[i][j] + max(dfs(i + 1, j, k), dfs(i, j + 1, k));18      if (coins[i][j] < 0 && k > 0) {19        ans = max({ans, dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)});20      }21      return f[i][j][k] = ans;22    };23    return dfs(0, 0, 2);24  }25};

1class Solution:2    def maximumAmount(self, coins: List[List[int]]) -> int: @ cache def dfs(i: int, j: int, k: int) -> int: if i >= m or j >= n: return - inf if i == m - 1 and j == n - 1: return max(coins[i][j], 0) if k else coins[i][j] ans = coins[i][j] + max(dfs(i + 1, j, k), dfs(i, j + 1, k)) if coins[i][j] < 0 and k: ans = max(ans, dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1)) return ans m, n = len(coins), len(coins[0]) return dfs(0, 0, 2)

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.

← Previous

Previous problem

Next problem