Loading... > https://leetcode.cn/problems/cherry-pickup/description/?envType=daily-question&envId=2024-05-06 ### DFS (TLE) 题目要求走到 `(n - 1, n - 1)` 后再回到 `(0, 0)` ，并找到能采集最多的樱桃。我首先想到的是用 `visited` 数组记录走过的路，然后使用 DFS 求解： ```c++ class Solution { public: int cherryPickup(std::vector<std::vector<int>>& grid) { const int n = grid.size(); int res = 0; std::vector<std::vector<bool>> visited(n, std::vector<bool>(n)); std::function<void(const int &, const int &, int, bool)> dfs = [&] (const int &i, const int &j, int cherry, bool back) { if (i == n || j == n || i == -1 || j == -1) return; if (grid[i][j] == -1) return; if (!visited[i][j] && grid[i][j] == 1) ++cherry; if (i == n - 1 && j == n - 1) back = true; if (back && i == 0 && j == 0) { if (cherry > res) res = cherry; return; } if (back) { dfs(i - 1, j, cherry, back); dfs(i, j - 1, cherry, back); } else { visited[i][j] = true; dfs(i + 1, j, cherry, back); dfs(i, j + 1, cherry, back); visited[i][j] = false; } }; dfs(0, 0, 0, false); return res; } }; ``` DFS 的 时间复杂度来到了 $ O(n^4)$ ，即使 $n$ 最大只有 50 ，也是会超时的。 ### DP 显然该问题具有最优子结构。但回去路上能采集到的樱桃受来的路线影响，这时候把问题看成两个人同时从 `(0, 0)` 出发到 `(n - 1, n - 1)` 即可。 由于每个格子的樱桃只能采摘一次，所以需要判断一下两个人什么时候会踩到同一个格子上。不妨令两人同时出发且速度相同，此时两人走过的格子数为同一个数 $k$ 。设两人的坐标分别为 $(x_1, y_1)$ ，$(x_2, y_2)$ ，那么有 $x_1 + y_1 = x_2 + y_2 = k$ 。根据此式易知：当 $x_1 = x_2$ 时，必有 $y_1 = y_2$ ，即两人走到了同一个格子。 此时就可以使用 DP 求解了。令 $dp[k][x_1][x_2]$ 为两个人走到 $(x_1, k - x_1)$ ， $(x_2, k - x_2)$ 时候采摘到的樱桃总数，有四种情况： - 两人都往右走：从 $dp[k - 1][x_1][x_2]$ 转移过来； - 第一人往右走，第二人往下走：从 $dp[k - 1][x_1][x_2 - 1]$ 转移过来； - 第一人往下走，第二人往右走：从 $dp[k - 1][x_1 - 1][x_2]$ 转移过来； - 两人都往下走：从 $dp[k - 1][x_1 - 1][x_2 - 1]$ 转移过来； 若遇到 $(x_1, y_1)$ 或 $(x_2, y_2)$ 处为荆棘，将该位置的 $dp$ 值设为 $-\infty$ 即可。 取四种情况的最大值，然后再加上 $grid[x_1][k - x_1]$ 和 $grid[x_2][k - x_2]$ 即可。若 $x_1 = x_2$ ，则只需加上一个。 ```c++ class Solution { public: int cherryPickup(std::vector<std::vector<int>>& grid) { const int n = grid.size(); std::vector<std::vector<std::vector<int>>> dp(2 * n - 1, std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MIN))); dp[0][0][0] = grid[0][0]; for (int k = 1; k < 2 * n - 1; ++k) { for (int x1 = std::max(k - n + 1, 0), y1; x1 <= std::min(k, n - 1); ++x1) { y1 = k - x1; if (grid[x1][y1] == -1) continue; for (int x2 = x1, y2; x2 <= std::min(k, n - 1); ++x2) { y2 = k - x2; if (grid[x2][y2] == -1) continue; int curCherries = dp[k - 1][x1][x2]; if (x1) curCherries = std::max(curCherries, dp[k - 1][x1 - 1][x2]); if (x2) curCherries = std::max(curCherries, dp[k - 1][x1][x2 - 1]); if (x1 && x2) curCherries = std::max(curCherries, dp[k - 1][x1 - 1][x2 - 1]); curCherries += grid[x1][y1]; if (x1 != x2) curCherries += grid[x2][y2]; dp[k][x1][x2] = curCherries; } } } return std::max(dp.back().back().back(), 0); } }; ``` - 时间复杂度：$O(n^3)$ ，其中 $n$ 为 `grid` 数组的长度。 - 空间复杂度：$O(n^3)$ 。 ### 压缩 DP 观察上述状态转移式，可以发现 $dp[k]$ 的结果只和 $dp[k - 1]$ 有关，所以可以把 dp 数组压缩成二维。为了保持前一步的状态不变，使用倒序遍历即可。 ```c++ class Solution { public: int cherryPickup(std::vector<std::vector<int>>& grid) { const int n = grid.size(); std::vector<std::vector<int>> dp(n, std::vector<int>(n, INT_MIN)); dp[0][0] = grid[0][0]; for (int k = 1; k < 2 * n - 1; ++k) { for (int x1 = std::min(k, n - 1), y1; x1 >= std::max(k - n + 1, 0); --x1) { y1 = k - x1; for (int x2 = std::min(k, n - 1), y2; x2 >= x1; --x2) { y2 = k - x2; if (grid[x1][y1] == -1 || grid[x2][y2] == -1) { dp[x1][x2] = INT_MIN; continue; } int curCherries = dp[x1][x2]; if (x1) curCherries = std::max(curCherries, dp[x1 - 1][x2]); if (x2) curCherries = std::max(curCherries, dp[x1][x2 - 1]); if (x1 && x2) curCherries = std::max(curCherries, dp[x1 - 1][x2 - 1]); curCherries += grid[x1][y1]; if (x1 != x2) curCherries += grid[x2][y2]; dp[x1][x2] = curCherries; } } } return std::max(dp.back().back(), 0); } }; ``` - 时间复杂度：$O(n^3)$ ，其中 $n$ 为数组 `grid` 的长度。 - 空间复杂度：$O(n^2)$ 。 最后修改：2024 年 05 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏