Medium

题目描述

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

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

  • 如果 coins[i][j] >= 0，机器人获得相应数量的金币。
  • 如果 coins[i][j] < 0，机器人遇到强盗，强盗会偷走 coins[i][j] 绝对值数量的金币。

机器人有一个特殊能力，可以在路径上最多 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 次中和能力的最大金币收益。这里 k 的取值范围是 0 到 2。

状态转移：对于每个位置 (i, j)，机器人可以从上方 (i-1, j) 或左方 (i, j-1) 到达。对于每种到达方式和每种中和能力使用次数，我们需要考虑两种选择：

  1. 不使用中和能力：直接获得/失去 coins[i][j] 的金币
  2. 使用中和能力（如果 coins[i][j] < 0 且还有剩余次数）：将负数位置中和为 0，避免损失

初始化：起始位置 (0, 0) 需要特殊处理，同样考虑是否对起始位置使用中和能力。

优化考虑：由于只能向右或向下移动，可以使用滚动数组优化空间复杂度，但为了代码清晰度，这里使用完整的三维数组。

时间复杂度为 O(m×n×3)，空间复杂度为 O(m×n×3)。

推荐解法：使用三维DP数组，状态转移时考虑所有可能的中和能力使用情况，确保找到全局最优解。

代码实现

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, INT_MIN)));
        
        // 初始化起始位置
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0][0][1] = 0; // 使用一次中和能力
        }
        
        // 填充第一行
        for (int j = 1; j < n; j++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[0][j-1][k] != INT_MIN) {
                    // 不使用中和能力
                    dp[0][j][k] = max(dp[0][j][k], dp[0][j-1][k] + coins[0][j]);
                    // 使用中和能力（如果可能）
                    if (k < 2 && coins[0][j] < 0) {
                        dp[0][j][k+1] = max(dp[0][j][k+1], dp[0][j-1][k]);
                    }
                }
            }
        }
        
        // 填充第一列
        for (int i = 1; i < m; i++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[i-1][0][k] != INT_MIN) {
                    // 不使用中和能力
                    dp[i][0][k] = max(dp[i][0][k], dp[i-1][0][k] + coins[i][0]);
                    // 使用中和能力（如果可能）
                    if (k < 2 && coins[i][0] < 0) {
                        dp[i][0][k+1] = max(dp[i][0][k+1], dp[i-1][0][k]);
                    }
                }
            }
        }
        
        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                for (int k = 0; k <= 2; k++) {
                    // 从上方来
                    if (dp[i-1][j][k] != INT_MIN) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k] + coins[i][j]);
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i-1][j][k]);
                        }
                    }
                    // 从左方来
                    if (dp[i][j-1][k] != INT_MIN) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k] + coins[i][j]);
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j-1][k]);
                        }
                    }
                }
            }
        }
        
        return max({dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2]});
    }
};

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        dp = [[[float('-inf')] * 3 for _ in range(n)] for _ in range(m)]
        
        # 初始化起始位置
        dp[0][0][0] = coins[0][0]
        if coins[0][0] < 0:
            dp[0][0][1] = 0  # 使用一次中和能力
        
        # 填充第一行
        for j in range(1, n):
            for k in range(3):
                if dp[0][j-1][k] != float('-inf'):
                    # 不使用中和能力
                    dp[0][j][k] = max(dp[0][j][k], dp[0][j-1][k] + coins[0][j])
                    # 使用中和能力（如果可能）
                    if k < 2 and coins[0][j] < 0:
                        dp[0][j][k+1] = max(dp[0][j][k+1], dp[0][j-1][k])
        
        # 填充第一列
        for i in range(1, m):
            for k in range(3):
                if dp[i-1][0][k] != float('-inf'):
                    # 不使用中和能力
                    dp[i][0][k] = max(dp[i][0][k], dp[i-1][0][k] + coins[i][0])
                    # 使用中和能力（如果可能）
                    if k < 2 and coins[i][0] < 0:
                        dp[i][0][k+1] = max(dp[i][0][k+1], dp[i-1][0][k])
        
        # 填充其余位置
        for i in range(1, m):
            for j in range(1, n):
                for k in range(3):
                    # 从上方来
                    if dp[i-1][j][k] != float('-inf'):
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k] + coins[i][j])
                        if k < 2 and coins[i][j] < 0:
                            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i-1][j][k])
                    # 从左方来
                    if dp[i][j-1][k] != float('-inf'):
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k] + coins[i][j])
                        if k < 2 and coins[i][j] < 0:
                            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j-1][k])
        
        return max(dp[m-1][n-1])

public class Solution {
    public int MaximumAmount(int[][] coins) {
        int m = coins.Length, n = coins[0].Length;
        int[,,] dp = new int[m, n, 3];
        
        // 初始化为极小值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i, j, k] = int.MinValue;
                }
            }
        }
        
        // 初始化起始位置
        dp[0, 0, 0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0, 0, 1] = 0; // 使用一次中和能力
        }
        
        // 填充第一行
        for (int j = 1; j < n; j++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[0, j-1, k] != int.MinValue) {
                    // 不使用中和能力
                    dp[0, j, k] = Math.Max(dp[0, j, k], dp[0, j-1, k] + coins[0][j]);
                    // 使用中和能力（如果可能）
                    if (k < 2 && coins[0][j] < 0) {
                        dp[0, j, k+1] = Math.Max(dp[0, j, k+1], dp[0, j-1, k]);
                    }
                }
            }
        }
        
        // 填充第一列
        for (int i = 1; i < m; i++) {
            for (int k = 0; k <= 2; k++) {
                if (dp[i-1, 0, k] != int.MinValue) {
                    // 不使用中和能力
                    dp[i, 0, k] = Math.Max(dp[i, 0, k], dp[i-1, 0, k] + coins[i][0]);
                    // 使用中和能力（如果可能）
                    if (k < 2 && coins[i][0] < 0) {
                        dp[i, 0, k+1] = Math.Max(dp[i, 0, k+1], dp[i-1, 0, k]);
                    }
                }
            }
        }
        
        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                for (int k = 0; k <= 2; k++) {
                    // 从上方来
                    if (dp[i-1, j, k] != int.MinValue) {
                        dp[i, j, k] = Math.Max(dp[i, j, k], dp[i-1, j, k] + coins[i][j]);
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i, j, k+1] = Math.Max(dp[i, j, k+1], dp[i-1, j, k]);
                        }
                    }
                    // 从左方来
                    if (dp[i, j-1, k] != int.MinValue) {
                        dp[i, j, k] = Math.Max(dp[i, j, k], dp[i, j-1, k] + coins[i][j]);
                        if (k < 2 && coins[i][j] < 0) {
                            dp[i, j, k+1] = Math.Max(dp[i, j, k+1], dp[i, j-1, k]);
                        }
                    }
                }
            }
        }
        
        return Math.Max(Math.Max(dp[m-1, n-1, 0], dp[m-1, n-1, 1]), dp[m-1, n-1, 2]);
    }
}

var maximumAmount = function(coins) {
    const m = coins.length, n = coins[0].length;
    const dp = Array(m).fill().map(() => 
        Array(n).fill().map(() => Array(3).fill(-Infinity))
    );
    
    // 初始化起始位置
    dp[0][0][0] = coins[0][0];
    if (coins[0][0] < 0) {
        dp[0][0][1] = 0; // 使用一次中和能力
    }
    
    // 填充第一行
    for (let j = 1; j < n; j++) {
        for (let k = 0; k <= 2; k++) {
            if (dp[0][j-1][k] !== -Infinity) {
                // 不使用中和能力
                dp[0][j][k] = Math.max(dp[0][j][k], dp[0][j-1][k] + coins[0][j]);
                // 使用中和能力（如果可能）
                if (k < 2 && coins[0][j] < 0) {
                    dp[0][j][k+1] = Math.max(dp[0][j][k+1], dp[0][j-1][k]);
                }
            }
        }
    }
    
    // 填充第一列
    for (let i = 1; i < m; i++) {
        for (let k = 0; k <= 2; k++) {
            if (dp[i-1][0][k] !== -Infinity) {
                // 不使用中和能力
                dp[i][0][k] = Math.max(dp[i][0][k], dp[i-1][0][k] + coins[i][0]);
                // 使用中和能力（如果可能）
                if (k < 2 && coins[i][0] < 0) {
                    dp[i][0][k+1] = Math.max(dp[i][0][k+1], dp[i-1][0][k]);
                }
            }
        }
    }
    
    // 填充其余位置
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            for (let k = 0; k <= 2; k++) {
                // 从上方来
                if (dp[i-1][j][k] !== -Infinity) {
                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j][k] + coins[i][j]);
                    if (k < 2 && coins[i][j] < 0) {
                        dp[i][j][k+1] = Math.max(dp[i][j][k+1], dp[i-1][j][k]);
                    }
                }
                // 从左方来
                if (dp[i][j-1][k] !== -Infinity) {
                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j-1][k] + coins[i][j]);
                    if (k < 2 && coins[i][j] < 0) {
                        dp[i][j][k+1] = Math.max(dp[i][j][k+1], dp[i][j-1][k]);
                    }
                }
            }
        }
    }
    
    return Math.max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
三维动态规划O(m × n × 3)O(m × n × 3)