每日一道leetcode2026.04.02机器人可以获得的最大金币数1. 题目2. 分析3. 代码实现4. 总结1. 题目给你一个 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] 10002. 分析终于来了一道中等难度的题了连着几天困难人麻了。这道题题目一读完就感觉和打家劫舍那道算法题特别像动态规划问题记得当时是判断当前这户抢与不强而当前的需要根据n-1和n-2判断以此类推。这道题我也想着从终点往回推终点的金币与左边和上边的有关感觉可以通过递归来套。但是这个问题难就难在有两次机会能够感化强盗这两次机会用在哪儿是关键。一开始我的实现逻辑是有次数就直接用执行通过了大部分的用例但是后面的给卡着了。根据题解的提示这个次数也应该是一个变量如果当前的金币数量为负并且感化次数大于0可以选择此时感化或不感化两种情况去递归取最终结果的较大值进行返回。整体逻辑还是比较好理解代码实现也简单。执行后后面的测试用例时出现超时即性能问题。按照题解的思路需要对计算过的dp[i][j][k]做记忆化也就是防止重复计算。比如3,3这个位置递归到2,3和3,2后这两个坐标点都会执行2,2的递归计算如果递归深度较大确实有很大的性能损耗。我首先想着是通过Map来记录每个dp[i][j][k]的最大值如果已经有了则执行返回实际执行的情况是也会超时查了下资料确实不如三维数组的效率高改成Integer[][][] memo new Integer[m][n][k 1]后执行通过注意是Integer类型默认值为null。最后一个维度为啥是k1呢因为有k1中可能比如题目的2次机会那么就有2次1次0次机会三种情况。3. 代码实现classSolution{publicintmaximumAmount(int[][]coins){intmcoins.length;intncoins[0].length;intk2;Integer[][][]memonewInteger[m][n][k1];returnmaximumAmount(coins,m-1,n-1,2,memo);}publicintmaximumAmount(int[][]coins,intcurrentRow,intcurrentCol,intk,Integer[][][]memo){if(currentRow0||currentCol0){returnInteger.MIN_VALUE;}if(memo[currentRow][currentCol][k]!null){returnmemo[currentRow][currentCol][k];}intcurrentCoinscoins[currentRow][currentCol];if(currentRow0currentCol0){intrescurrentCoins0k0?0:currentCoins;memo[currentRow][currentCol][k]res;returnres;}intdefaultMaxcurrentCoinsMath.max(maximumAmount(coins,currentRow,currentCol-1,k,memo),maximumAmount(coins,currentRow-1,currentCol,k,memo));if(currentCoins0||k0){// 如果当前位置的硬币大于0则只能选择当前位置的硬币memo[currentRow][currentCol][k]defaultMax;returndefaultMax;}// 当前位置的硬币小于0选择感化和不感化两种情况进行递归再比较最终的结果intresMath.max(defaultMax,Math.max(maximumAmount(coins,currentRow,currentCol-1,k-1,memo),maximumAmount(coins,currentRow-1,currentCol,k-1,memo)));memo[currentRow][currentCol][k]res;returnres;}}4. 总结吃一堑长一智dp动态规划算法问题经验1其实我还有个问题原题目描述的话语中“机器人有一项特殊能力可以在行程中 最多感化 2个单元格的强盗从而防止这些单元格的金币被抢走”这个防止被抢走是指的已经攒的金币不被抢走还是当前这个单元格数量对应的绝对值数量金币不被抢走呢从最终结果来看是抢走已有的金币。之前还有其它题也有类似的疑惑有时一道题题目理解都需要花费不少时间不知道你是否经历过同样的烦恼。