题目描述

给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。

网格中的每个单元格包含一个值 coins[i][j]：

• 如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
• 如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。

机器人有一项特殊能力，可以在行程中 最多感化 2 个单元格的强盗，从而防止这些单元格的金币被抢走。

注意：机器人的总金币数可以是负数。

返回机器人在路径上可以获得的 最大金币数。

样例

输入： 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）。

输入： 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

算法

(动态规划) $O(mn)$

1. 设状态 $f(i, j, k)$ 表示到达了格子 $(i, j)$，恰好用了 $k$ 次感化的最大金币数。
2. 初始时，$f(0, 0, 0) = coins(0, 0)$，如果 $coins(0, 0) < 0$，则 $f(0, 0, 1) = 0$。其余状态为 $-\infty$。
3. 转移时，对于 $f(i, j, k)$，转移 $f(i, j, k) = \max(f(i - 1, j, k), f(i, j - 1, k)) + coins(i, j)$，如果 $coins(i, j) < 0$ 且 $k > 0$，则可以再从 $f(i - 1, j, k - 1)$ 或者 $f(i, j - 1, k - 1)$ 转移。
4. 最终答案为 $\max(f(m - 1, n - 1, k))$。

时间复杂度

• 状态数为 $O(mn)$，转移时间为常数，故总时间复杂度为 $O(mn)$。

空间复杂度

• 需要 $O(mn)$ 的额外空间存储状态。

C++ 代码

const int N = 510, INF = 1000000000;

class Solution {
private:
    int f[N][N][3];

public:
    int maximumAmount(vector<vector<int>>& coins) {
        const int m = coins.size(), n = coins[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k <= 2; k++)
                    f[i][j][k] = -INF;

        f[0][0][0] = coins[0][0];
        if (coins[0][0] < 0)
            f[0][0][1] = 0;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k <= 2; k++) {
                    if (i > 0) {
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + coins[i][j]);
                        if (coins[i][j] < 0 && k > 0)
                            f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1]);
                    }

                    if (j > 0) {
                        f[i][j][k] = max(f[i][j][k], f[i][j - 1][k] + coins[i][j]);
                        if (coins[i][j] < 0 && k > 0)
                            f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1]);
                    }
                }

        return max(f[m - 1][n - 1][0], max(f[m - 1][n - 1][1], f[m - 1][n - 1][2]));
    }
};