Skip to content

3418. Maximum Amount of Money Robot Can Earn 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
class Solution {
 public:
  int maximumAmount(vector<vector<int>>& coins) {
    const int m = coins.size();
    const int n = coins[0].size();
    // dp[i][j][k] := the maximum profit at position (i, j) with k remaining
    // neutralizations
    vector<vector<vector<int>>> dp(
        m, vector<vector<int>>(n, vector<int>(4, -INT_MAX / 2)));

    // Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0];
    if (coins[0][0] < 0)
      dp[0][0][1] = 0;  // Neutralize the robber.

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int k = 0; k < 3; ++k) {
          if (i > 0)
            dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k] + coins[i][j],
                               dp[i - 1][j][k + 1]});
          if (j > 0)
            dp[i][j][k] = max({dp[i][j][k], dp[i][j - 1][k] + coins[i][j],
                               dp[i][j - 1][k + 1]});
        }

    return ranges::max(dp[m - 1][n - 1]);
  }
};

 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
class Solution {
  public int maximumAmount(int[][] coins) {
    final int m = coins.length;
    final int n = coins[0].length;
    // dp[i][j][k] := the maximum profit at position (i, j) with k remaining neutralizations
    int[][][] dp = new int[m][n][4];
    Arrays.stream(dp).forEach(
        A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, Integer.MIN_VALUE / 2)));

    // Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0];
    if (coins[0][0] < 0)
      dp[0][0][1] = 0; // Neutralize the robber.

    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < 3; k++) {
          if (i > 0)
            dp[i][j][k] =
                Math.max(dp[i][j][k], Math.max(dp[i - 1][j][k] + coins[i][j], dp[i - 1][j][k + 1]));
          if (j > 0)
            dp[i][j][k] =
                Math.max(dp[i][j][k], Math.max(dp[i][j - 1][k] + coins[i][j], dp[i][j - 1][k + 1]));
        }

    return Arrays.stream(dp[m - 1][n - 1]).max().getAsInt();
  }
}

 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
class Solution:
  def maximumAmount(self, coins: list[list[int]]) -> int:
    m = len(coins)
    n = len(coins[0])
    # dp[i][j][k] := the maximum profit at position (i, j) with k remaining
    # neutralizations
    dp = [[[-math.inf] * 4 for _ in range(n)] for _ in range(m)]

    # Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0]
    if coins[0][0] < 0:
      dp[0][0][1] = 0  # Neutralize the robber.

    for i in range(m):
      for j in range(n):
        for k in range(3):  # for each number of remaining neutralizations
          if i > 0:
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i - 1][j][k] + coins[i][j],
                              dp[i - 1][j][k + 1])
          if j > 0:
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i][j - 1][k] + coins[i][j],
                              dp[i][j - 1][k + 1])

    return max(dp[-1][-1])