LeetCode 题解工作台
机器人可以获得的最大金币数
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1) 。在任意时刻，机器人只能向右或向下移动。 网格中的每个单元格包含一个值 coins[i][j] ： 如果 coins[i][j] >= 0 ，机器人可以获得该单元格的金币…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, j, k)$，表示机器人从 $(i, j)$ 出发，还剩下 次感化机会时，能够获得的最大金币数。机器人只能向右或向下移动，因此 $\textit{dfs}(i, j, k)$ 的值只与 $\textit{dfs}(i + 1, j, k)$ 和 $\textit{dfs}(i, j + 1, k)$ 有关。 - 如果 $i \geq m$ 或 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 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.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示机器人从 出发，还剩下 次感化机会时，能够获得的最大金币数。机器人只能向右或向下移动，因此 的值只与 和 有关。
- 如果 或 ，表示机器人走出了网格，此时返回一个极小值。
- 如果 且 ，表示机器人到达了网格的右下角，此时如果 ，则机器人可以选择感化当前位置的强盗，因此返回 ；如果 ，则机器人不能感化当前位置的强盗，因此返回 。
- 如果 ，表示当前位置有强盗，此时如果 ，则机器人可以选择感化当前位置的强盗，因此返回 ；如果 ，则机器人不能感化当前位置的强盗，因此返回 。
根据上述分析，我们可以编写出记忆化搜索的代码。
时间复杂度 ，空间复杂度 。其中 和 分别是二维数组 的行数和列数，而 是感化机会的状态数，本题中 。
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])
ans = dfs(0, 0, 2)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the final approach, but in the general case, it will be O(m * n) because we visit each cell once. Space complexity can be optimized to O(n) by using only the current and previous rows for the dynamic programming table. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate effectively utilizes dynamic programming to solve the problem.
- question_mark
Candidate identifies and handles the robber neutralization aspect appropriately.
- question_mark
Candidate demonstrates awareness of space optimization techniques in dynamic programming.
常见陷阱
外企场景- error
Failing to correctly account for robber neutralization, leading to suboptimal paths.
- error
Overcomplicating the dynamic programming solution and using unnecessary space.
- error
Not considering edge cases, such as grids with only one row or one column.
进阶变体
外企场景- arrow_right_alt
What if the robot can neutralize more than two robbers?
- arrow_right_alt
How would the solution change if the robot can move diagonally?
- arrow_right_alt
What if negative coins are not allowed in the grid?