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 ofcoins[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:
- Start at
(0, 0)with0coins (total coins =0). - Move to
(0, 1), gaining1coin (total coins =0 + 1 = 1). - Move to
(1, 1), where there's a robber stealing2coins. The robot uses one neutralization here, avoiding the robbery (total coins =1). - Move to
(1, 2), gaining3coins (total coins =1 + 3 = 4). - Move to
(2, 2), gaining4coins (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:
- Start at
(0, 0)with10coins (total coins =10). - Move to
(0, 1), gaining10coins (total coins =10 + 10 = 20). - Move to
(0, 2), gaining another10coins (total coins =20 + 10 = 30). - Move to
(1, 2), gaining the final10coins (total coins =30 + 10 = 40).
Constraints:
m == coins.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000
Solutions
This code solves a path traversal problem where you collect coins from a grid while moving only right or down, with the ability to negate (ignore) at most 2 negative values. It uses dynamic programming with a 3D table dp[row][col][k] that tracks the maximum coins you can collect up to position (row, col) using exactly k negations (where k ranges from 0 to 2). The algorithm initializes the starting cell, then fills the first row and column by considering only downward or rightward moves, and finally fills the rest of the grid by taking the best path from above or the left. When encountering a negative coin value, the code decides whether to add it to your sum or use a negation to skip it entirely, keeping the previous best value instead. At the end, it returns the Math.max() of all three states at the bottom-right corner, representing the best possible score using 0, 1, or 2 negations.
/**
* @param {number[][]} coins
* @return {number}
*/
var maximumAmount = function(coins) {
const m = coins.length;
const n = coins[0].length;
const dp = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(3).fill(0)));
dp[0][0][0] = coins[0][0];
dp[0][0][1] = coins[0][0] < 0 ? 0 : coins[0][0];
dp[0][0][2] = coins[0][0] < 0 ? 0 : coins[0][0];
for (let row = 1; row < m; row++) {
const val = coins[row][0];
dp[row][0][0] = val + dp[row - 1][0][0];
dp[row][0][1] = val + dp[row - 1][0][1];
dp[row][0][2] = val + dp[row - 1][0][2];
if (val < 0) {
dp[row][0][1] = Math.max(dp[row][0][1], dp[row - 1][0][0]);
dp[row][0][2] = Math.max(dp[row][0][2], dp[row - 1][0][1]);
}
}
for (let col = 1; col < n; col++) {
const val = coins[0][col];
dp[0][col][0] = val + dp[0][col - 1][0];
dp[0][col][1] = val + dp[0][col - 1][1];
dp[0][col][2] = val + dp[0][col - 1][2];
if (val < 0) {
dp[0][col][1] = Math.max(dp[0][col][1], dp[0][col - 1][0]);
dp[0][col][2] = Math.max(dp[0][col][2], dp[0][col - 1][1]);
}
}
//console.log(dp);
for (let row = 1; row < m; row++) {
for (let col = 1; col < n; col++) {
const val = coins[row][col];
dp[row][col][0] = val + Math.max(dp[row - 1][col][0], dp[row][col - 1][0]);
dp[row][col][1] = val + Math.max(dp[row - 1][col][1], dp[row][col - 1][1]);
dp[row][col][2] = val + Math.max(dp[row - 1][col][2], dp[row][col - 1][2]);
if (val < 0) {
dp[row][col][1] = Math.max(
dp[row][col][1],
dp[row - 1][col][0],
dp[row][col - 1][0],
);
dp[row][col][2] = Math.max(
dp[row][col][2],
dp[row - 1][col][1],
dp[row][col - 1][1],
);
}
}
}
//console.log(dp);
return Math.max(...dp[m - 1][n - 1]);
};