3418. Maximum Amount of Money Robot Can Earn

📘 題目敘述

給定一個 m × n 的矩陣 coins。

機器人一開始位在左上角 (0, 0)，目標是走到右下角 (m - 1, n - 1)。
在移動過程中，每一步只能：

往右走
往下走

每個格子都有一個數值 coins[i][j]：

如果 coins[i][j] >= 0，代表機器人可以拿到這麼多金幣
如果 coins[i][j] < 0，代表遇到 robber，機器人會被搶走 abs(coins[i][j]) 枚金幣

另外，機器人有一個特殊能力：

最多可以在路徑上的 2 個格子中 neutralize robber
如果在某個負數格使用這個能力，就不會被扣金幣

注意：機器人最後的總金幣數可能是負的。

請回傳從左上走到右下時，機器人最多可以拿到多少金幣。

條件限制

m == coins.length
n == coins[i].length
1 <= m, n <= 500
-1000 <= coins[i][j] <= 1000

🧠 解題思路

我這題的想法是用三維 DP。

因為一般走格子 DP 只需要記：

目前走到哪個位置

但這題還多了一個狀態：

到目前為止已經用了幾次 neutralization

所以我把 DP 狀態設成：

dp[i][j][k]
代表走到 (i, j) 時，已經用了 k 次 neutralization 的最大金幣數

這樣每次轉移時，就分成兩種情況：

不使用 neutralization，那就直接把 coins[i][j] 加上去
如果目前格子是負數，而且還能用 neutralization，那就可以選擇「不扣這格的錢」，改從 k - 1 的狀態轉過來

最後右下角可能有用了 0、1、2 次 neutralization 三種情況，所以把三者最大值取出來就是答案。

所有變數

m：矩陣列數
n：矩陣行數
dp：三維 DP，dp[i][j][k] 代表走到 (i, j) 且已經用了 k 次 neutralization 時，最多能拿到的金幣數

🪜 主要流程步驟

1. 先定義 DP 狀態

我先建立一個三維 DP：

這裡第三維大小是 3，因為 neutralization 最多只能用 2 次，
所以狀態會是：

0：目前一次都還沒用
1：目前已經用了 1 次
2：目前已經用了 2 次

初始值我先設成一個很小的負數，表示這個狀態目前還到不了。

2. 先初始化起點 `(0, 0)`

起點一定會經過，所以要先處理它。

如果起點是一般非負數格，那很直接：

dp[0][0][0] = coins[0][0];

代表：

走到起點
還沒用任何 neutralization
總金幣就是起點那格的值

如果起點本身是負數，我這份寫法還多處理了一種情況：

if (coins[0][0] < 0) {
    dp[0][0][1] = 0;
}

意思是可以直接在起點就用一次 neutralization，
這樣起點這格雖然是 robber，但不會扣錢，所以總金幣會變成 0。

3. 枚舉每個格子，從上方或左方轉移過來

接著我用兩層迴圈掃整個矩陣。
每個位置 (i, j) 都只可能從：

上方 (i - 1, j)
左方 (i, j - 1)

走過來。

所以對每個 k，我都先考慮「這格不使用 neutralization」的轉移。

如果可以從上方來，就更新：

dp[i][j][k] =
    max(dp[i][j][k], dp[i - 1][j][k] + coins[i][j]);

如果可以從左方來，就更新：

dp[i][j][k] =
    max(dp[i][j][k], dp[i][j - 1][k] + coins[i][j]);

這兩段的意思都一樣：

前一格已經用了 k 次 neutralization
這一格我不額外使用能力
所以直接把目前格子的值 coins[i][j] 加上去

4. 如果目前格子是負數，也可以選擇在這格使用 neutralization

這題最重要的地方就是這個額外轉移。

如果目前這格是負數，而且 k > 0，
表示我現在可以考慮把其中一次 neutralization 用在這一格。

這樣的話，這一格就不會扣錢，
所以我不需要加上 coins[i][j]，而是直接從「前一格用了 k - 1 次」的狀態轉過來。

這段意思是：

原本到前一格時只用了 k - 1 次能力
現在走進這格，剛好多用一次
因為這格 robber 被 neutralize 了，所以這格不扣錢

也就是把「正常吃下這格負數」和「在這格開能力跳過扣分」這兩種情況一起比較，取比較大的那個。

5. 起點以外的每個格子，都要把三種 `k` 狀態都更新完

我在每個 (i, j) 都跑：

這表示我不是只記一個最佳值，
而是分開記：

走到這格、用了 0 次能力的最佳值
走到這格、用了 1 次能力的最佳值
走到這格、用了 2 次能力的最佳值

這樣後面才不會把不同能力使用次數的情況混在一起。

因為「目前金幣較大」不一定代表未來就比較好，
有時候現在少拿一點，但保留更多 neutralization，之後反而更有利。
所以第三維狀態一定要獨立記。

6. 最後在右下角三種狀態中取最大值

當整個 DP 做完之後，右下角 (m - 1, n - 1) 會有三個狀態：

dp[m - 1][n - 1][0]
dp[m - 1][n - 1][1]
dp[m - 1][n - 1][2]

它們分別代表走到終點時，總共用了 0、1、2 次 neutralization 的最大金幣數。

所以最後直接取三者最大值：

return (int)max(
    {dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});

這就是答案。

⏱️ 複雜度

設 m = coins.length，n = coins[0].length。

時間複雜度：O(mn)
每個格子都只會處理固定 3 種 neutralization 狀態，而且每次只看上方和左方。
空間複雜度：O(mn)
我用了 m × n × 3 的 DP 陣列，常數 3 可以忽略，所以記成 O(mn)。

💻 程式碼實作

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();
        vector<vector<vector<long long>>> dp(
            m, vector<vector<long long>>(n, vector<long long>(3, -1e8)));
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0][0][1] = 0;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                for (int k = 0; k <= 2; k++) {
                    if (i > 0) {
                        dp[i][j][k] =
                            max(dp[i][j][k], dp[i - 1][j][k] + coins[i][j]);
                    }
                    if (j > 0) {
                        dp[i][j][k] =
                            max(dp[i][j][k], dp[i][j - 1][k] + coins[i][j]);
                    }
                    if (coins[i][j] < 0 && k > 0) {
                        if (i > 0) {
                            dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1]);
                        }
                        if (j > 0) {
                            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1]);
                        }
                    }
                }
            }
        }
        return (int)max(
            {dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});
    }
};

🔗 題目連結

https://leetcode.com/problems/maximum-amount-of-money-robot-can-earn/