We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Amount of Money Robot Can Earn

Difficulty: Medium

Problem 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. Return the maximum profit the robot can gain on the route.

Key Insights

  • The robot can only move right or down, which means the path from (0,0) to (m-1,n-1) is constrained.
  • The robot can neutralize at most 2 robbers, allowing for strategic decisions on where to use these neutralizations for maximum profit.
  • A dynamic programming approach can be utilized to keep track of the maximum coins collected at each cell while considering the robbers and neutralizations.

Space and Time Complexity

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

Solution

We can use a dynamic programming approach where we maintain a 3D array dp[i][j][k], where i and j represent the current cell in the grid and k represents the number of robbers neutralized (0, 1, or 2). We will iterate through each cell in the grid, calculating the maximum coins that can be collected considering the movement options (from the top or left cell) and the effect of neutralizing robbers. The final result will be found in dp[m-1][n-1][0], dp[m-1][n-1][1], or dp[m-1][n-1][2].

Code Solutions

def maxCoins(coins):
    m, n = len(coins), len(coins[0])
    dp = [[[-float('inf')] * 3 for _ in range(n)] for _ in range(m)]
    
    dp[0][0][0] = coins[0][0] if coins[0][0] >= 0 else 0
    if coins[0][0] < 0:
        dp[0][0][1] = -coins[0][0]
    
    for i in range(m):
        for j in range(n):
            for k in range(3):
                if i == 0 and j == 0:
                    continue
                if i > 0:
                    current = dp[i-1][j][k]
                    if coins[i][j] >= 0:
                        dp[i][j][k] = max(dp[i][j][k], current + coins[i][j])
                    else:
                        if k > 0:
                            dp[i][j][k] = max(dp[i][j][k], current)
                            dp[i][j][k] = max(dp[i][j][k], current + coins[i][j])
                if j > 0:
                    current = dp[i][j-1][k]
                    if coins[i][j] >= 0:
                        dp[i][j][k] = max(dp[i][j][k], current + coins[i][j])
                    else:
                        if k > 0:
                            dp[i][j][k] = max(dp[i][j][k], current)
                            dp[i][j][k] = max(dp[i][j][k], current + coins[i][j])
    
    return max(dp[m-1][n-1])
← Back to All Questions