M3418.机器人可以获得的最大金币数

dp, https://leetcode.cn/problems/maximum-amount-of-money-robot-can-earn/

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

这是一个经典的动态规划问题，通过增加一个维度来记录“剩余的感化次数”。

解题思路

状态定义：定义 dp[i][j][k] 为机器人到达单元格 (i, j) 且此时剩余 k 次感化机会时能获得的最大金币数。其中：
- 0 <= i < m
- 0 <= n < n
- k \in {0, 1, 2}
转移方程：机器人可以从左边 (i, j-1) 或上边 (i-1, j) 移动过来。在每一个位置 (i, j)，我们有两种选择：
- 不使用感化能力：无论 coins[i][j] 是正是负，都直接加上它的值。 dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]) + coins[i][j]
- 使用感化能力（仅当 coins[i][j] < 0 且 k > 0 时）：如果感化当前位置，则当前位置贡献的金币视为 0，且消耗一次机会。 dp[i][j][k-1] = max(dp[i][j][k-1], max(dp[i-1][j][k], dp[i][j-1][k]) + 0)
初始化：由于金币数可能为负，我们将 dp 数组初始化为负无穷大。起始位置 dp[0][0][2] 的值为 coins[0][0]。如果 coins[0][0] < 0，则 dp[0][0][1]（感化一次）的值为 0。
空间优化：由于 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-1]，我们可以通过滚动数组优化空间，但为了代码可读性，以下使用标准三维数组实现。
Python 代码实现

python

from typing import List

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        # dp[i][j][k] 表示到达 (i, j) 且还有 k 次感化机会时的最大金币
        # k 取值 0, 1, 2
        inf = float('inf')
        dp = [[[-inf] * 3 for _ in range(n)] for _ in range(m)]
        
        # 初始化起点 (0, 0)
        # 不感化
        dp[0][0][2] = coins[0][0]
        # 如果是负数，可以选择感化
        if coins[0][0] < 0:
            dp[0][0][1] = 0
            # 也可以连续感化两次（虽然在这个格子感化一次就够了，但逻辑上允许）
            # 但题目要求最多感化，感化正数没有意义，所以只考虑负数感化为0
            dp[0][0][0] = 0
        else:
            # 如果 (0,0) 是正数，感化它没有收益，维持原值
            dp[0][0][1] = coins[0][0]
            dp[0][0][0] = coins[0][0]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                
                for k in range(3):
                    res = -inf
                    # 从上方来
                    if i > 0:
                        res = max(res, dp[i-1][j][k])
                    # 从左方来
                    if j > 0:
                        res = max(res, dp[i][j-1][k])
                    
                    # 选项1：不感化当前格
                    dp[i][j][k] = max(dp[i][j][k], res + coins[i][j])
                    
                    # 选项2：感化当前格 (前提是当前格是负数且有剩余次数)
                    if coins[i][j] < 0 and k > 0:
                        dp[i][j][k-1] = max(dp[i][j][k-1], res)
                    # 如果当前是正数，感化没意义，状态平移（或者由不感化逻辑覆盖）
                    if coins[i][j] >= 0 and k > 0:
                         dp[i][j][k-1] = max(dp[i][j][k-1], res + coins[i][j])

        return max(dp[m-1][n-1])

复杂度分析

时间复杂度： $O (m \times n \times 3)$ ，即 $O (m \times n)$ 。我们需要遍历网格中的每一个点，并对每个点处理 3 种感化状态。
空间复杂度： $O (m \times n \times 3)$ 。使用了三维数组存储状态。在 $m, n \leq 500$ 的情况下，该复杂度是可以接受的。

M3418.机器人可以获得的最大金币数 ​

M3418.机器人可以获得的最大金币数