Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.
You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.
Return the maximum number of cherries collection using both robots by following the rules below:
- From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
- When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
- When both robots stay on the same cell, only one of them takes the cherries.
- Both robots cannot move outside of the grid at any moment.
- Both robots should reach the bottom row in the
grid.
Example 1:
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]] Output: 24 Explanation: Path of robot #1 and #2 are described in color green and blue respectively. Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12. Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12. Total of cherries: 12 + 12 = 24.
Example 2:
Input: 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]] Output: 28 Explanation: Path of robot #1 and #2 are described in color green and blue respectively. Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17. Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11. Total of cherries: 17 + 11 = 28.
Example 3:
Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]] Output: 22
Example 4:
Input: grid = [[1,1],[1,1]] Output: 4
Constraints:
rows == grid.lengthcols == grid[i].length2 <= rows, cols <= 700 <= grid[i][j] <= 100
Solution: DP
dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)
dp[y][x1][x2] = max(dp[y+1][x1 + dx1][x2 + dx2]) -1 <= dx1, dx2 <= 1
Time complexity: O(c^2*r)
Space complexity: O(c^2*r)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Author: Huahua class Solution { public: int cherryPickup(vector<vector<int>>& grid) { const int r = grid.size(); const int c = grid[0].size(); vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1))); function<int(int, int, int)> dp = [&](int y, int x1, int x2) { if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0; int& ans = cache[y][x1][x2]; if (ans != -1) return ans; const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2]; for (int d1 = -1; d1 <= 1; ++d1) for (int d2 = -1; d2 <= 1; ++d2) ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2)); return ans; }; return dp(0, 0, c - 1); } }; |
Bottom-up
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int cherryPickup(vector<vector<int>>& grid) { const int r = grid.size(); const int c = grid[0].size(); vector<vector<vector<int>>> dp(r + 2, vector<vector<int>>(c + 2, vector<int>(c + 2))); for (int y = r; y >= 1; --y) for (int x1 = 1; x1 <= c; ++x1) for (int x2 = 1; x2 <= c; ++x2) { const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1]; int& ans = dp[y][x1][x2]; for (int d1 = -1; d1 <= 1; ++d1) for (int d2 = -1; d2 <= 1; ++d2) ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]); } return dp[1][1][c]; } }; |
O(c^2) Space
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int cherryPickup(vector<vector<int>>& grid) { const int r = grid.size(); const int c = grid[0].size(); vector<vector<int>> dp(c + 2, vector<int>(c + 2)); for (int y = r; y >= 1; --y) { vector<vector<int>> tmp(c + 2, vector<int>(c + 2)); for (int x1 = 1; x1 <= c; ++x1) for (int x2 = 1; x2 <= c; ++x2) { const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1]; for (int d1 = -1; d1 <= 1; ++d1) for (int d2 = -1; d2 <= 1; ++d2) tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]); } dp.swap(tmp); } return dp[1][c]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment