Problem Statement in English

You’re given a 2D grid of integers grid of size m x n, where grid[i][j] represents the amount of money at cell (i, j).

A robot starts at the top-left corner of the grid and wants to reach the bottom-right corner.

The robot can only move either down or right at any point in time.

However, the robot has a special ability that allows it to shoot up to 2 times. When the robot shoots, it can skip collecting money from a cell with a negative value (i.e., it can treat that cell as if it has a value of 0).

Return the maximum amount of money the robot can earn by the time it reaches the bottom-right corner of the grid.

Approach

To solve this problem, we can use dynamic programming. We will create a 3D DP array dp[i][j][k] where i and j represent the current cell in the grid, and k represents the number of shots used (0, 1, or 2).

The value of dp[i][j][k] will represent the maximum amount of money the robot can earn starting from cell (i, j) with k shots used.

The base case will be the bottom-right corner of the grid, where we can directly take the value of that cell (considering if we need to use a shot or not).

And then we just work our way backwards to the top-left corner, considering the possible moves (right and down) and whether we want to use a shot or not when we encounter a negative value.

Finally, the answer will be in dp[0][0][2], which represents the maximum amount of money the robot can earn starting from the top-left corner with up to 2 shots available.

And we’re done!

Solution in Python


class Solution:
    def maximumAmount(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        dp = [[[-inf]*3 for _ in range(N)] for _ in range(M)]

        # base case (bottom-right)
        for k in range(3):
            if grid[M-1][N-1] < 0 and k > 0:
                dp[M-1][N-1][k] = 0
            else:
                dp[M-1][N-1][k] = grid[M-1][N-1]

        for i in reversed(range(M)):
            for j in reversed(range(N)):
                if i == M-1 and j == N-1:
                    continue

                for shots in range(3):
                    best = -inf

                    # move right
                    if j + 1 < N:
                        best = max(best, grid[i][j] + dp[i][j+1][shots])
                        if grid[i][j] < 0 and shots > 0:
                            best = max(best, dp[i][j+1][shots-1])

                    # move down
                    if i + 1 < M:
                        best = max(best, grid[i][j] + dp[i+1][j][shots])
                        if grid[i][j] < 0 and shots > 0:
                            best = max(best, dp[i+1][j][shots-1])

                    dp[i][j][shots] = best

        return dp[0][0][2]

Complexity

  • Time: $O(M \times N \times 3)$
    Where M and N are the dimensions of the grid, and we iterate through each cell and each possible number of shots (0, 1, or 2).

  • Space: $O(M \times N \times 3)$
    Where M and N are the dimensions of the grid, and we store the maximum amount of money for each cell and each possible number of shots.

And we are done.