LeetCode Solutions Blog

Maximum Amount of Money Robot Can Earn

Number: 3677

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n grid where each cell contains a coin value (which could be positive or negative), a robot starts at the top‑left cell (0, 0) and can only move right or down to reach the bottom‑right cell (m‑1, n‑1). If a cell has a non-negative number, the robot gains that many coins. If the cell is negative, it represents a robber that steals the absolute value of the coins. The robot is allowed to neutralize robbers in at most 2 cells along its path. The goal is to determine the maximum profit (total coins gained, which can be negative) the robot can achieve while traversing a valid path.

Key Insights

Use dynamic programming because movements are restricted (only right and down) and optimal substructure exists.
Keep track of the count of neutralizations used. Use a 3-dimensional DP state: dp[i][j][k] where (i, j) is the cell and k is the number of neutralizations used (0, 1, or 2).
Update the DP from the top-left cell towards the bottom-right cell considering both options at a cell with a negative coin value: taking the negative value or using a neutralization (if available) to avoid loss.
The final answer will be the maximum profit at the bottom-right cell using up to 2 neutralizations.

Space and Time Complexity

Time Complexity: O(m * n * 3) = O(m * n)
Space Complexity: O(m * n * 3) = O(m * n)

Solution

We solve the problem using dynamic programming with three dimensions to track:

The current cell (i, j) in the grid.
The count of neutralizations used so far (0 to 2).

For every cell, we consider two possible moves: right and down. When processing a cell:

If the cell has a non-negative value, we simply add it to the current profit.
If the cell has a negative value (indicating a robber), we have two choices: a. Do not use a neutralization and add the negative value. b. If we haven’t used up 2 neutralizations, use one and add 0 for that cell.

The dp state is updated accordingly from the top-left to bottom-right cell, and the maximum value at the destination using any count of neutralizations (0, 1, or 2) is returned.

Code Solutions

# Python solution for Maximum Amount of Money Robot Can Earn

def max_profit(coins):
    # Get the dimensions of the grid
    m, n = len(coins), len(coins[0])
    
    # Initialize dp with -infinity. dp[i][j][k] represents the best profit 
    # arriving at cell (i, j) with k neutralizations used
    dp = [[[-float("inf")] * 3 for _ in range(n)] for _ in range(m)]
    
    # Start at (0, 0)
    # If no robber, simply add coin value; if robber and we can use neutralization, choose max option.
    # For start cell, initialize both states if applicable.
    initial_value = coins[0][0]
    if initial_value >= 0:
        # Only one possibility: add the coin value, no neutralization needed
        dp[0][0][0] = initial_value
    else:
        # Two possibilities: take negative value without neutralization, or neutralize it if possible.
        dp[0][0][0] = initial_value  # not neutralized
        if 2 > 0:  # we have possibility to use up a neutralization
            dp[0][0][1] = 0  # use one neutralization to avoid loss
    
    # Process each cell in the grid
    for i in range(m):
        for j in range(n):
            for used in range(3):
                if dp[i][j][used] == -float("inf"):
                    continue  # skip unreachable states
                
                # Iterate over possible moves: right and down
                for ni, nj in ((i + 1, j), (i, j + 1)):
                    if ni >= m or nj >= n:
                        continue
                    
                    coin = coins[ni][nj]
                    # If coin is non-negative, no need to use neutralization
                    if coin >= 0:
                        # Update state without using an extra neutralization
                        if dp[ni][nj][used] < dp[i][j][used] + coin:
                            dp[ni][nj][used] = dp[i][j][used] + coin
                    else:
                        # Negative value: Option 1 -> Do not use neutralization and accept loss
                        if dp[ni][nj][used] < dp[i][j][used] + coin:
                            dp[ni][nj][used] = dp[i][j][used] + coin
                        # Option 2 -> Use neutralization if available (if used < 2)
                        if used < 2:
                            if dp[ni][nj][used + 1] < dp[i][j][used]:
                                dp[ni][nj][used + 1] = dp[i][j][used]
    
    # The answer is the maximum over all states (0, 1, or 2 neutralizations used) at bottom-right cell.
    return max(dp[m-1][n-1])

# Example usage:
coins1 = [[0, 1, -1], [1, -2, 3], [2, -3, 4]]
print(max_profit(coins1))  # Expected output: 8

coins2 = [[10,10,10],[10,10,10]]
print(max_profit(coins2))  # Expected output: 40