目标
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。
网格中的每个单元格包含一个值 coins[i][j]：
- 如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
- 如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。
机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。
注意：机器人的总金币数可以是负数。
返回机器人在路径上可以获得的 最大金币数 。
示例 1：
输入： coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
输出： 8
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。示例 2：
输入： coins = [[10,10,10],[10,10,10]]
输出： 40
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 10（总金币 = 10）。
移动到 (0, 1)，获得 10 枚金币（总金币 = 10 + 10 = 20）。
移动到 (0, 2)，再获得 10 枚金币（总金币 = 20 + 10 = 30）。
移动到 (1, 2)，获得 10 枚金币（总金币 = 30 + 10 = 40）。说明：
- m == coins.length
- n == coins[i].length
- 1 <= m, n <= 500
- -1000 <= coins[i][j] <= 1000
思路
有一个 m x n 的网格图，一个机器人从左上角 (0, 0) 向右或者向下移动直到 (m - 1, n - 1)。在此过程中可以收集对应格子上的金币，如果金币大于等于 0，则收集对应数量的金币，否则失去对应数量的金币。机器人有两次机会避免失去金币（感化），求可以获得的最大金币数量。
定义 dp[i][j][k] 表示到达 (i, j) 最多感化 k 次收集到的最大金币数，状态转移方程为：
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + coins[i][j]，不感化从上方与左方转移而来，加上当前格子金币dp[i][j][1] = Math.max(Math.max(dp[i - 1][j][0], dp[i][j - 1][0]), Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j])，感化，不计入当前格子金币，感化次数加一，不感化，计入当前格子金币，感化次数不变dp[i][j][2] = Math.max(Math.max(dp[i - 1][j][1], dp[i][j - 1][1]), Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j])，同上
代码
/**
* @date 2026-04-02 8:44
*/
public class MaximumAmount3418 {
public int maximumAmount(int[][] coins) {
int m = coins.length;
int n = coins[0].length;
int[][][] dp = new int[m][n][3];
dp[0][0][0] = coins[0][0];
dp[0][0][1] = Math.max(0, coins[0][0]);
dp[0][0][2] = Math.max(0, dp[0][0][1]);
for (int j = 1; j < n; j++) {
dp[0][j][0] = dp[0][j - 1][0] + coins[0][j];
dp[0][j][1] = Math.max(dp[0][j - 1][0], dp[0][j - 1][1] + coins[0][j]);
dp[0][j][2] = Math.max(dp[0][j - 1][1], dp[0][j - 1][2] + coins[0][j]);
}
for (int i = 1; i < m; i++) {
dp[i][0][0] = dp[i - 1][0][0] + coins[i][0];
dp[i][0][1] = Math.max(dp[i - 1][0][0], dp[i - 1][0][1] + coins[i][0]);
dp[i][0][2] = Math.max(dp[i - 1][0][1], dp[i - 1][0][2] + coins[i][0]);
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + coins[i][j];
dp[i][j][1] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]);
dp[i][j][1] = Math.max(dp[i][j][1], Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j]);
dp[i][j][2] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]);
dp[i][j][2] = Math.max(dp[i][j][2], Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j]);
}
}
return dp[m - 1][n - 1][2];
}
}
性能
