Maximum Amount of Money Robot Can Earn

Medium Dynamic Programming 2D DP Original on LeetCode

Reported atPhonePe

Maximum Amount of Money Robot Can Earn is a medium dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (3d dp over cell and neutralizations used), runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every path and every choice) up.

Problem

A robot starts at the top-left cell (0, 0) of an m × n grid and must reach the bottom-right cell (m - 1, n - 1), moving only right or down at each step.

Each cell holds a value coins[i][j]. If it is non-negative, the robot collects that many coins. If it is negative, a robber is waiting there and takes |coins[i][j]| coins from the robot. The robot may neutralize at most 2 robbers along its path; a neutralized cell takes nothing. The total may become negative.

Return the maximum total the robot can hold when it reaches the bottom-right cell.

Examples

Example 1

Input
coins = [[2, -4, 1], [-3, 5, -6], [1, -2, 3]]
Output
10
Why
Path 2 → -4 → 5 → -2 → 3: neutralize both robbers and collect 2 + 0 + 5 + 0 + 3 = 10.

Example 2

Input
coins = [[-5, -1, -2, -7]]
Output
-3
Why
The only path meets four robbers. Neutralizing the two worst ones (-5 and -7) leaves -1 - 2 = -3.

Example 3

Input
coins = [[4, 6], [1, 8]]
Output
18
Why
No robbers; 4 → 6 → 8 is the richer of the two paths.

Constraints

  • m == coins.length, n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every path and every choice)O(3^(m+n))O(m + n)
Optimal (3D DP over cell and neutralizations used)O(m · n)O(m · n)

1Brute force (try every path and every choice)

TimeO(3^(m+n))Every step branches into two directions and possibly two choices, so the number of explored paths grows exponentially.
SpaceO(m + n)Recursion depth equals the path length m + n - 1.

Recursively walk from (0, 0): at each cell either collect its value, or, if it is a robber and a neutralization is left, spend one and collect 0. Then continue right or down and keep the better result.

  1. best(i, j, left) = max over the choices at this cell of (gain + best of the next cell).
  2. At the bottom-right cell there is no next cell; return the gain.
  3. Return best(0, 0, 2).
class Solution {
    private int[][] g;
    private int m, n;

    private int best(int i, int j, int left) {
        int v = g[i][j];
        int result = Integer.MIN_VALUE;
        for (int use = 0; use <= 1; use++) {
            if (use == 1 && (v >= 0 || left == 0)) continue;
            int gain = use == 1 ? 0 : v;
            int rem = left - use;
            if (i == m - 1 && j == n - 1) {
                result = Math.max(result, gain);
                continue;
            }
            int next = Integer.MIN_VALUE;
            if (i + 1 < m) next = Math.max(next, best(i + 1, j, rem));
            if (j + 1 < n) next = Math.max(next, best(i, j + 1, rem));
            result = Math.max(result, gain + next);
        }
        return result;
    }

    public int maximumAmount(int[][] coins) {
        g = coins;
        m = coins.length;
        n = coins[0].length;
        return best(0, 0, 2);
    }
}

2Optimal (3D DP over cell and neutralizations used)

TimeO(m · n)Three states per cell, each computed from at most four predecessors.
SpaceO(m · n)The table stores 3 values per cell (one row would suffice).

dp[i][j][u] is the most money the robot can hold on reaching (i, j) after using exactly u neutralizations. The predecessor is the better of the cell above and the cell to the left with the same u (collect the value), or, on a robber cell, with u - 1 (collect nothing).

  1. Fill dp row by row; unreachable states hold a very negative sentinel.
  2. prev(u) = max(dp[i-1][j][u], dp[i][j-1][u]), or 0 for u = 0 at the start cell.
  3. dp[i][j][u] = prev(u) + v; if v < 0 and u > 0, also try prev(u - 1).
  4. Return the maximum of dp[m-1][n-1][0..2].
class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length, n = coins[0].length;
        final int NEG = Integer.MIN_VALUE / 4;
        int[][][] dp = new int[m][n][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int v = coins[i][j];
                int[] prev = new int[3];
                for (int u = 0; u < 3; u++) {
                    if (i == 0 && j == 0) prev[u] = u == 0 ? 0 : NEG;
                    else {
                        int p = NEG;
                        if (i > 0) p = Math.max(p, dp[i - 1][j][u]);
                        if (j > 0) p = Math.max(p, dp[i][j - 1][u]);
                        prev[u] = p;
                    }
                }
                for (int u = 0; u < 3; u++) {
                    int best = prev[u] == NEG ? NEG : prev[u] + v;
                    if (v < 0 && u > 0 && prev[u - 1] != NEG) best = Math.max(best, prev[u - 1]);
                    dp[i][j][u] = best;
                }
            }
        }
        return Math.max(dp[m - 1][n - 1][0], Math.max(dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]));
    }
}

Edge cases to test

  • A 1 × 1 grid (the start is the end; a robber there can be neutralized)
  • More than two robbers on every path: the two worst ones should be neutralized
  • All cells negative: the answer is negative
  • A single row or column (only one path)

Hints

Hint 1

Without robbers this is the classic maximum path sum moving right or down. What extra information does each cell need?

Hint 2

Add a third dimension: how many neutralizations have been used so far (0, 1 or 2).

Hint 3

dp[i][j][u] = best total at (i, j) having used u neutralizations. Either take coins[i][j] and keep u, or, on a robber cell, take 0 and come from a state with u - 1.

FAQ

What is the best time complexity for Maximum Amount of Money Robot Can Earn?

Optimal (3D DP over cell and neutralizations used) runs in O(m · n) time and O(m · n) extra space. Three states per cell, each computed from at most four predecessors.

Which pattern does Maximum Amount of Money Robot Can Earn use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Maximum Amount of Money Robot Can Earn?

Yes. Brute force (try every path and every choice) takes O(3^(m+n)) time and O(m + n) space. Recursively walk from (0, 0): at each cell either collect its value, or, if it is a robber and a neutralization is left, spend one and collect 0.

Which edge cases should I test for Maximum Amount of Money Robot Can Earn?

A 1 × 1 grid (the start is the end; a robber there can be neutralized); More than two robbers on every path: the two worst ones should be neutralized; All cells negative: the answer is negative; A single row or column (only one path).