LeetCode 3418：机器人获取最大金币数（动态规划+状态压缩）

LeetCode 3418机器人获取最大金币数动态规划状态压缩LeetCode 3418. 机器人可以获得的最大金币数【动态规划状态压缩】问题描述给定一个m x n的网格机器人从左上角(0, 0)出发前往右下角(m-1, n-1)仅能向右或向下移动。单元格值≥0机器人获得该单元格对应的金币单元格值0机器人遇到强盗会被抢走该单元格数值绝对值的金币机器人拥有特殊能力最多可感化 2 个强盗单元格感化后可避免被该单元格的强盗抢金币要求返回机器人在路径上可以获得的最大金币数注意总金币数可为负数。解题思路核心分析移动限制机器人仅能向右或向下移动无回头路径从起点到终点的总步数固定为mn-2横向走n-1步、纵向走m-1步。关键变量核心约束是“最多使用2次感化能力”因此需要在状态中记录感化次数区分0、1、2次三种场景。算法选择采用三维动态规划适配“位置感化次数”的双状态需求具体定义如下dp[i][j][k]表示机器人到达网格(i,j)位置且已使用k次感化能力k0、1、2时能获得的最大金币数。状态转移转移来源机器人到达(i,j)只能从两个方向过来——上方(i-1,j)或 左方(i,j-1)取两个方向的最大值作为转移基础。单元格处理逻辑根据当前单元格coins[i][j]的值分两种情况处理且仅在遇到强盗单元格时才涉及感化能力的使用若coins[i][j] ≥ 0直接累加该单元格的金币不消耗感化次数状态转移时k值保持不变。若coins[i][j] 0强盗单元格不使用感化能力金币数减去该单元格数值的绝对值即直接加上coins[i][j]因为其本身为负数k值不变。使用感化能力消耗1次感化次数k1金币数不增不减即保持转移前的金币数且需保证k1 ≤ 2不超过最大感化次数。边界条件起点初始化单独处理(0,0)位置根据该单元格的值区分是否使用感化能力初始化dp[0][0][0]和必要时dp[0][0][1]。第一行与第一列第一行仅能从左侧单元格转移而来第一列仅能从上方单元格转移而来需单独填充避免数组越界。完整代码LeetCode 3418 完整AC代码from typing import List class Solution: def maximumAmount(self, coins: List[List[int]]) - int: m len(coins) n len(coins[0]) INF float(-inf) # 三维DPdp[i][j][k] 表示到达(i,j)用了k次感化的最大金币 (k0,1,2) dp [[[INF] * 3 for _ in range(n)] for __ in range(m)] # 初始化起点 (0,0) val coins[0][0] if val 0: dp[0][0][0] val else: dp[0][0][0] val # 不使用感化直接扣钱 dp[0][0][1] 0 # 使用1次感化不扣钱 # 填充第一行仅能从左侧转移 for j in range(1, n): curr coins[0][j] for k in range(3): prev dp[0][j-1][k] if prev INF: # 左侧位置不可达跳过 continue if curr 0: dp[0][j][k] max(dp[0][j][k], prev curr) else: # 不使用感化扣钱 dp[0][j][k] max(dp[0][j][k], prev curr) # 使用感化不扣钱消耗1次次数 if k 1 3: dp[0][j][k1] max(dp[0][j][k1], prev) # 填充第一列仅能从上方转移 for i in range(1, m): curr coins[i][0] for k in range(3): prev dp[i-1][0][k] if prev INF: # 上方位置不可达跳过 continue if curr 0: dp[i][0][k] max(dp[i][0][k], prev curr) else: # 不使用感化扣钱 dp[i][0][k] max(dp[i][0][k], prev curr) # 使用感化不扣钱消耗1次次数 if k 1 3: dp[i][0][k1] max(dp[i][0][k1], prev) # 填充剩余网格可从上方或左侧转移 for i in range(1, m): for j in range(1, n): curr coins[i][j] for k in range(3): # 取上方和左侧的最大金币数作为转移基础 from_up dp[i-1][j][k] from_left dp[i][j-1][k] max_prev max(from_up, from_left) if max_prev INF: # 两个来源都不可达跳过 continue if curr 0: dp[i][j][k] max(dp[i][j][k], max_prev curr) else: # 不使用感化扣钱 dp[i][j][k] max(dp[i][j][k], max_prev curr) # 使用感化不扣钱消耗1次次数 if k 1 3: dp[i][j][k1] max(dp[i][j][k1], max_prev) # 终点的三种感化状态0/1/2次取最大值即为答案 return max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])代码解析1. 初始化定义三维DP数组dp默认值设为负无穷INF表示初始状态下所有位置均不可达。单独处理起点(0,0)若起点是金币单元格直接将dp[0][0][0]设为该金币值若起点是强盗单元格分别初始化“不使用感化”扣钱和“使用1次感化”不扣钱两种状态。2. 边界填充第一行机器人只能从左侧单元格转移而来遍历每一列依次处理“金币单元格”和“强盗单元格”的状态转移跳过不可达的左侧位置。第一列机器人只能从上方单元格转移而来逻辑与第一行一致遍历每一行处理状态转移跳过不可达的上方位置。3. 主体转移遍历网格中除第一行、第一列以外的所有单元格对每个单元格执行以下操作先获取“上方”和“左方”单元格在当前感化次数k下的最大金币数max_prev若两个来源均不可达则跳过该状态。若当前单元格是金币单元格直接将max_prev加上单元格值更新dp[i][j][k]。若当前单元格是强盗单元格分两种情况更新状态——不使用感化扣钱、使用感化消耗1次次数不扣钱确保感化次数不超过2次。4. 结果输出机器人到达终点(m-1, n-1)后存在三种可能的状态使用0、1、2次感化能力取这三种状态的最大值即为机器人能获得的最大金币数。复杂度分析时间复杂度O(m×n×3)O(mn)O(m \times n \times 3) O(mn)O(m×n×3)O(mn)。网格共有m \times n个单元格每个单元格需处理3种感化状态操作均为常数级效率极高可轻松通过题目给定的500×500数据范围。空间复杂度O(m×n×3)O(mn)O(m \times n \times 3) O(mn)O(m×n×3)O(mn)。三维DP数组存储所有状态可通过“滚动数组”优化为O(n)O(n)O(n)仅保留当前行和上一行的状态进一步降低空间消耗。测试示例示例 1示例1测试代码coins [[0,1,-1],[1,-2,3],[2,-3,4]] print(Solution().maximumAmount(coins)) # 输出8解析最优路径为(0,0) → (0,1) → (1,1) → (1,2) → (2,2)其中在(1,1)位置使用1次感化能力避免被扣2枚金币最终总金币为 010348。示例 2示例2测试代码coins [[10,10,10],[10,10,10]] print(Solution().maximumAmount(coins)) # 输出40解析所有单元格均为金币单元格无需使用感化能力最优路径为(0,0) → (0,1) → (0,2) → (1,2)总金币为 1010101040。总结本题是网格路径DP的经典进阶题型核心难点在于“感化次数”的状态记录——通过三维DP的第三维精准捕捉“位置感化次数”的双重状态完美适配题目约束。解题关键的两点一是明确状态转移的两个来源上、左二是区分强盗单元格的两种处理方式使用/不使用感化。代码逻辑清晰、注释完整可直接复制提交AC适合初学者学习网格DP的状态设计与转移思路。补充提示若需优化空间复杂度可将三维DP简化为二维仅保留当前行的3种感化状态核心转移逻辑不变感兴趣的同学可自行尝试实现。