Skip to content

3418. Maximum Amount of Money Robot Can Earn

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

Solution:

class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] memo = new int[m][n][3];
        for (int[][] mat : memo) {
            for (int[] row : mat) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }
        }
        return dfs(m - 1, n - 1, 2, coins, memo);
    }

    private int dfs(int i, int j, int k, int[][] coins, int[][][] memo) {
        if (i < 0 || j < 0) {
            return Integer.MIN_VALUE;
        }
        int x = coins[i][j];
        if (i == 0 && j == 0) {
            return k > 0 ? Math.max(x, 0) : x;
        }
        if (memo[i][j][k] != Integer.MIN_VALUE) { // 之前计算过
            return memo[i][j][k];
        }
        int res = Math.max(dfs(i - 1, j, k, coins, memo), dfs(i, j - 1, k, coins, memo)) + x; // 选
        if (k > 0 && x < 0) {
            res = Math.max(res, Math.max(dfs(i - 1, j, k - 1, coins, memo), dfs(i, j - 1, k - 1, coins, memo))); // 不选
        }
        return memo[i][j][k] = res; // 记忆化
    }
}

class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] f = new int[m + 1][n + 1][3];
        for (int[] row : f[0]) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        for (int i = 0; i < m; i++) {
            Arrays.fill(f[i + 1][0], Integer.MIN_VALUE);
            for (int j = 0; j < n; j++) {
                int x = coins[i][j];
                if (i == 0 && j == 0) {
                    f[1][1][0] = x;
                    f[1][1][1] = f[1][1][2] = Math.max(x, 0);
                    continue;
                }
                f[i + 1][j + 1][0] = Math.max(f[i + 1][j][0], f[i][j + 1][0]) + x;
                f[i + 1][j + 1][1] = Math.max(
                        Math.max(f[i + 1][j][1], f[i][j + 1][1]) + x,
                        Math.max(f[i + 1][j][0], f[i][j + 1][0])
                );
                f[i + 1][j + 1][2] = Math.max(
                        Math.max(f[i + 1][j][2], f[i][j + 1][2]) + x,
                        Math.max(f[i + 1][j][1], f[i][j + 1][1])
                );
            }
        }
        return f[m][n][2];
    }
}

Reference

https://leetcode.cn/problems/maximum-amount-of-money-robot-can-earn/solutions/3045103/wang-ge-tu-dp-by-endlesscheng-g96j/