Hard

题目描述

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。grid[i][j] 代表单元格 (i, j) 上的樱桃数量。

你有两个机器人可以为你收集樱桃：

  • 机器人 #1 从左上角单元格 (0, 0) 出发
  • 机器人 #2 从右上角单元格 (0, cols - 1) 出发

请你按照如下规则，返回两个机器人可以收集的樱桃数目的最大值：

  • 从单元格 (i, j) 出发，机器人可以移动到单元格 (i + 1, j - 1)、(i + 1, j) 或者 (i + 1, j + 1)
  • 当一个机器人经过某个单元格时，它会收集该单元格内所有的樱桃，然后该单元格变成空单元格
  • 当两个机器人同时到达同一个单元格时，只有一个机器人可以收集该单元格内的樱桃
  • 两个机器人在任意时刻都不能移动到网格外面
  • 两个机器人最后都要到达网格最下面一行

示例 1：

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 #1 和机器人 #2 的路径用绿色和蓝色分别表示。
机器人 #1 收集的樱桃：(3 + 2 + 5 + 2) = 12
机器人 #2 收集的樱桃：(1 + 5 + 5 + 1) = 12
樱桃总数：12 + 12 = 24

示例 2：

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28

提示：

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

解题思路

这是一个经典的双路径动态规划问题。我们需要同时考虑两个机器人的移动路径，关键在于将问题转化为状态转移。

核心思路：

  1. 状态定义：定义 dp[i][j1][j2] 表示在第 i 行，机器人1在列 j1，机器人2在列 j2 时能收集到的最大樱桃数

  2. 状态转移：两个机器人都只能向下移动（行数增加1），列数可以变化±1或不变。对于每个状态，我们需要考虑上一行的所有可能位置组合

  3. 边界条件：初始状态为 dp[0][0][cols-1] = grid[0][0] + grid[0][cols-1]（如果两个机器人在不同位置）

  4. 重复收集处理：当两个机器人在同一位置时（j1 == j2），樱桃只能被收集一次

优化策略：

  • 可以使用滚动数组优化空间复杂度，因为每一行的状态只依赖于上一行
  • 每个机器人有3种移动方向，所以总共需要考虑 3×3 = 9 种状态转移

时间复杂度分析：

  • 状态数：O(rows × cols²)
  • 每个状态的转移：O(9) = O(1)
  • 总时间复杂度：O(rows × cols²)

代码实现

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
        
        // 初始状态
        dp[0][0][cols - 1] = grid[0][0] + grid[0][cols - 1];
        
        // 填充dp表
        for (int i = 1; i < rows; i++) {
            for (int j1 = 0; j1 < cols; j1++) {
                for (int j2 = 0; j2 < cols; j2++) {
                    // 尝试所有可能的前一状态
                    for (int pj1 = j1 - 1; pj1 <= j1 + 1; pj1++) {
                        for (int pj2 = j2 - 1; pj2 <= j2 + 1; pj2++) {
                            if (pj1 >= 0 && pj1 < cols && pj2 >= 0 && pj2 < cols && dp[i - 1][pj1][pj2] != -1) {
                                int cherries = dp[i - 1][pj1][pj2] + grid[i][j1];
                                if (j1 != j2) {
                                    cherries += grid[i][j2];
                                }
                                dp[i][j1][j2] = max(dp[i][j1][j2], cherries);
                            }
                        }
                    }
                }
            }
        }
        
        // 找到最后一行的最大值
        int result = 0;
        for (int j1 = 0; j1 < cols; j1++) {
            for (int j2 = 0; j2 < cols; j2++) {
                result = max(result, dp[rows - 1][j1][j2]);
            }
        }
        
        return result;
    }
};

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[[-1] * cols for _ in range(cols)] for _ in range(rows)]
        
        # 初始状态
        dp[0][0][cols - 1] = grid[0][0] + grid[0][cols - 1]
        
        # 填充dp表
        for i in range(1, rows):
            for j1 in range(cols):
                for j2 in range(cols):
                    # 尝试所有可能的前一状态
                    for pj1 in range(max(0, j1 - 1), min(cols, j1 + 2)):
                        for pj2 in range(max(0, j2 - 1), min(cols, j2 + 2)):
                            if dp[i - 1][pj1][pj2] != -1:
                                cherries = dp[i - 1][pj1][pj2] + grid[i][j1]
                                if j1 != j2:
                                    cherries += grid[i][j2]
                                dp[i][j1][j2] = max(dp[i][j1][j2], cherries)
        
        # 找到最后一行的最大值
        result = 0
        for j1 in range(cols):
            for j2 in range(cols):
                result = max(result, dp[rows - 1][j1][j2])
        
        return result

public class Solution {
    public int CherryPickup(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        int[,,] dp = new int[rows, cols, cols];
        
        // 初始化为-1表示无效状态
        for (int i = 0; i < rows; i++) {
            for (int j1 = 0; j1 < cols; j1++) {
                for (int j2 = 0; j2 < cols; j2++) {
                    dp[i, j1, j2] = -1;
                }
            }
        }
        
        // 初始状态
        dp[0, 0, cols - 1] = grid[0][0] + grid[0][cols - 1];
        
        // 填充dp表
        for (int i = 1; i < rows; i++) {
            for (int j1 = 0; j1 < cols; j1++) {
                for (int j2 = 0; j2 < cols; j2++) {
                    // 尝试所有可能的前一状态
                    for (int pj1 = Math.Max(0, j1 - 1); pj1 <= Math.Min(cols - 1, j1 + 1); pj1++) {
                        for (int pj2 = Math.Max(0, j2 - 1); pj2 <= Math.Min(cols - 1, j2 + 1); pj2++) {
                            if (dp[i - 1, pj1, pj2] != -1) {
                                int cherries = dp[i - 1, pj1, pj2] + grid[i][j1];
                                if (j1 != j2) {
                                    cherries += grid[i][j2];
                                }
                                dp[i, j1, j2] = Math.Max(dp[i, j1, j2], cherries);
                            }
                        }
                    }
                }
            }
        }
        
        // 找到最后一行的最大值
        int result = 0;
        for (int j1 = 0; j1 < cols; j1++) {
            for (int j2 = 0; j2 < cols; j2++) {
                result = Math.Max(result, dp[rows - 1, j1, j2]);
            }
        }
        
        return result;
    }
}

var cherryPickup = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    const dp = Array(rows).fill().map(() => 
        Array(cols).fill().map(() => Array(cols).fill(-1))
    );
    
    // 初始状态
    dp[0][0][cols - 1] = grid[0][0] + grid[0][cols - 1];
    
    // 填充dp表
    for (let i = 1; i < rows; i++) {
        for (let j1 = 0; j1 < cols; j1++) {
            for (let j2 = 0; j2 < cols; j2++) {
                // 尝试所有可能的前一状态
                for (let pj1 = Math.max(0, j1 - 1); pj1 <= Math.min(cols - 1, j1 + 1); pj1++) {
                    for (let pj2 = Math.max(0, j2 - 1); pj2 <= Math.min(cols - 1, j2 + 1); pj2++) {
                        if (dp[i - 1][pj1][pj2] !== -1) {
                            let cherries = dp[i - 1][pj1][pj2] + grid[i][j1];
                            if (j1 !== j2) {
                                cherries += grid[i][j2];
                            }
                            dp[i][j1][j2] = Math.max(dp[i][j1][j2], cherries);
                        }
                    }
                }
            }
        }
    }
    
    // 找到最后一行的最大值
    let result = 0;
    for (let j1 = 0; j1 < cols; j1++) {
        for (let j2 = 0; j2 < cols; j2++) {
            result = Math.max(result, dp[rows - 1][j1][j2]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(rows × cols² × 9) = O(rows × cols²)状态数为 rows × cols²，每个状态转移需要考虑 9 种前置状态
空间复杂度O(rows × cols²)三维 DP 数组的空间开销，可以优化为 O(cols²)