Loading... > https://leetcode.cn/problems/cherry-pickup-ii/description/?envType=daily-question&envId=2024-05-06 ### DP 和昨天的题类似，同样是用 DP 求解。两个机器人分别从左上角和右上角出发，每次只能往下方三个有效格子内走，因此每个位置能采到的最多的樱桃为上方三个有效格子中最大值加上该位置的樱桃数。因为每个格子只能被采集一次，所以当两个机器人在同一个格子时，只需要加一次当前格子的樱桃数即可。 只能往下方三个有效格子内走，因此左边机器人的位置 $(x_1, y_1)$ 应该满足 $0 \leq x_1 \leq y_1$ ，同理右边机器人的位置 $(x_2, y_2)$ 应该满足 $y_2 \leq x_2 \leq cols$ ( $cols$ 为 `grid` 数组的列数)。 ```c++ class Solution { public: int cherryPickup(std::vector<std::vector<int>>& grid) { const int rows = grid.size(), cols = grid[0].size(); std::vector<std::vector<std::vector<int>>> dp(rows, std::vector<std::vector<int>>(cols, std::vector<int>(cols))); dp[0][0][cols - 1] = grid[0][0] + grid[0][cols - 1]; for (int row = 1, lLimit, rLimit, plLimit, prLimit, cherry; row < rows; ++row) { lLimit = std::min(row, cols - 1); for (int left = 0; left <= lLimit; ++left) { rLimit = std::max(cols - row - 1, 0); for (int right = cols - 1; right >= rLimit; --right) { plLimit = std::min(row - 1, cols - 1); prLimit = std::max(cols - row, 0); cherry = grid[row][left]; if (left != right) cherry += grid[row][right]; for (int lOffset = left - 1; lOffset <= left + 1; ++lOffset) { if (lOffset < 0 || lOffset > plLimit) continue; for (int rOffset = right - 1; rOffset <= right + 1; ++rOffset) { if (rOffset < prLimit || rOffset >= cols) continue; dp[row][left][right] = std::max(dp[row][left][right], dp[row - 1][lOffset][rOffset] + cherry); } } } } } int res = 0; for (int i = 0; i < cols; ++i) res = std::max(res, *std::max_element(dp.back()[i].begin(), dp.back()[i].end())); return res; } }; ``` - 时间复杂度：$O(m \times n^2)$ 。其中 $m$ 为 `grid` 数组的行数， $n$ 为 `grid` 数组的列数。 - 空间复杂度：$O(m \times n^2)$ 。 ### 压缩 DP 观察 `dp[i]` 只和 `dp[i - 1]` 有关，所以将三维 DP 压缩成二维。这里实现只需要用两个二维数组，存储上一个和当前的状态即可。 ```c++ class Solution { public: int cherryPickup(std::vector<std::vector<int>>& grid) { const int rows = grid.size(), cols = grid[0].size(); std::vector<std::vector<int>> prev(cols, std::vector<int>(cols)), cur(cols, std::vector<int>(cols)); prev[0][cols - 1] = grid[0][0] + grid[0][cols - 1]; for (int row = 1, lLimit, rLimit, plLimit, prLimit, cherry; row < rows; ++row) { lLimit = std::min(row, cols - 1); for (int left = 0; left <= lLimit; ++left) { rLimit = std::max(cols - row - 1, 0); for (int right = cols - 1; right >= rLimit; --right) { plLimit = std::min(row - 1, cols - 1); prLimit = std::max(cols - row, 0); cherry = grid[row][left]; if (left != right) cherry += grid[row][right]; for (int lOffset = left - 1; lOffset <= left + 1; ++lOffset) { if (lOffset < 0 || lOffset > plLimit) continue; for (int rOffset = right - 1; rOffset <= right + 1; ++rOffset) { if (rOffset < prLimit || rOffset >= cols) continue; cur[left][right] = std::max(cur[left][right], prev[lOffset][rOffset] + cherry); } } } } std::swap(cur, prev); } int res = 0; for (int i = 0; i < cols; ++i) res = std::max(res, *std::max_element(prev[i].begin(), prev[i].end())); return res; } }; ``` - 时间复杂度：$O(m \times n^2)$ 。其中 $m$ 为 `grid` 数组的行数， $n$ 为 `grid` 数组的列数。 - 空间复杂度：$O(n^2)$ 。 最后修改：2024 年 05 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏