Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    
  • 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);
        }
    };
    
    
  • 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)
    
    
  • 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)
    }
    
    
  • 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);
    }
    
    

All Problems

All Solutions