Skip to content

3418. Maximum Amount of Money Robot Can Earn

Description

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

Solutions

We design a function \(\textit{dfs}(i, j, k)\), which represents the maximum amount of coins the robot can collect starting from \((i, j)\) with \(k\) conversion opportunities left. The robot can only move right or down, so the value of \(\textit{dfs}(i, j, k)\) depends only on \(\textit{dfs}(i + 1, j, k)\) and \(\textit{dfs}(i, j + 1, k)\).

  • If \(i \geq m\) or \(j \geq n\), it means the robot has moved out of the grid, so we return a very small value.
  • If \(i = m - 1\) and \(j = n - 1\), it means the robot has reached the bottom-right corner of the grid. If \(k > 0\), the robot can choose to convert the bandit at the current position, so we return \(\max(0, \textit{coins}[i][j])\). If \(k = 0\), the robot cannot convert the bandit at the current position, so we return \(\textit{coins}[i][j]\).
  • If \(\textit{coins}[i][j] < 0\), it means there is a bandit at the current position. If \(k > 0\), the robot can choose to convert the bandit at the current position, so we return \(\textit{coins}[i][j] + \max(\textit{dfs}(i + 1, j, k), \textit{dfs}(i, j + 1, k))\). If \(k = 0\), the robot cannot convert the bandit at the current position, so we return \(\textit{coins}[i][j] + \max(\textit{dfs}(i + 1, j, k), \textit{dfs}(i, j + 1, k))\).

Based on the above analysis, we can write the code for memoized search.

The time complexity is \(O(m \times n \times k)\), and the space complexity is \(O(m \times n \times k)\). Here, \(m\) and \(n\) are the number of rows and columns of the 2D array \(\textit{coins}\), and \(k\) is the number of conversion opportunities, which is \(3\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func maximumAmount(coins [][]int) int {
    m, n := len(coins), len(coins[0])
    f := make([][][]int, m)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, 3)
            for k := range f[i][j] {
                f[i][j][k] = math.MinInt32
            }
        }
    }
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i >= m || j >= n {
            return math.MinInt32 / 2
        }
        if f[i][j][k] != math.MinInt32 {
            return f[i][j][k]
        }
        if i == m-1 && j == n-1 {
            if k > 0 {
                return max(0, coins[i][j])
            }
            return coins[i][j]
        }
        ans := coins[i][j] + max(dfs(i+1, j, k), dfs(i, j+1, k))
        if coins[i][j] < 0 && k > 0 {
            ans = max(ans, max(dfs(i+1, j, k-1), dfs(i, j+1, k-1)))
        }
        f[i][j][k] = ans
        return ans
    }
    return dfs(0, 0, 2)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function maximumAmount(coins: number[][]): number {
    const [m, n] = [coins.length, coins[0].length];
    const f = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => Array(3).fill(-Infinity)),
    );
    const dfs = (i: number, j: number, k: number): number => {
        if (i >= m || j >= n) {
            return -Infinity;
        }
        if (f[i][j][k] !== -Infinity) {
            return f[i][j][k];
        }
        if (i === m - 1 && j === n - 1) {
            return k > 0 ? Math.max(0, coins[i][j]) : coins[i][j];
        }
        let 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, dfs(i + 1, j, k - 1), dfs(i, j + 1, k - 1));
        }
        return (f[i][j][k] = ans);
    };
    return dfs(0, 0, 2);
}

Comments