调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

给你一个 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

解释:

一个获得最多金币的最优路径如下:

  1. (0, 0) 出发,初始金币为 0(总金币 = 0)。
  2. 移动到 (0, 1),获得 1 枚金币(总金币 = 0 + 1 = 1)。
  3. 移动到 (1, 1),遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力,避免被抢(总金币 = 1)。
  4. 移动到 (1, 2),获得 3 枚金币(总金币 = 1 + 3 = 4)。
  5. 移动到 (2, 2),获得 4 枚金币(总金币 = 4 + 4 = 8)。

示例 2:

输入: coins = [[10,10,10],[10,10,10]]

输出: 40

解释:

一个获得最多金币的最优路径如下:

  1. (0, 0) 出发,初始金币为 10(总金币 = 10)。
  2. 移动到 (0, 1),获得 10 枚金币(总金币 = 10 + 10 = 20)。
  3. 移动到 (0, 2),再获得 10 枚金币(总金币 = 20 + 10 = 30)。
  4. 移动到 (1, 2),获得 10 枚金币(总金币 = 30 + 10 = 40)。

 

提示:

  • m == coins.length
  • n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000
通过次数
4.6K
提交次数
10.8K
通过率
42.3%


相关企业

提示 1
Use Dynamic Programming.

提示 2
Let dp[i][j][k] denote the maximum amount of money a robot can earn by starting at cell (i,j) and having neutralized k robbers.

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
coins =
[[0,1,-1],[1,-2,3],[2,-3,4]]
Source