|
| 1 | +// https://leetcode.com/problems/cherry-pickup-ii/ |
| 2 | + |
| 3 | + |
| 4 | +// You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell. |
| 5 | + |
| 6 | +// You have two robots that can collect cherries for you: |
| 7 | + |
| 8 | +// Robot #1 is located at the top-left corner (0, 0), and |
| 9 | +// Robot #2 is located at the top-right corner (0, cols - 1). |
| 10 | +// Return the maximum number of cherries collection using both robots by following the rules below: |
| 11 | + |
| 12 | +// From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1). |
| 13 | +// When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell. |
| 14 | +// When both robots stay in the same cell, only one takes the cherries. |
| 15 | +// Both robots cannot move outside of the grid at any moment. |
| 16 | +// Both robots should reach the bottom row in grid. |
| 17 | + |
| 18 | + |
| 19 | +Solution: |
| 20 | + |
| 21 | +#include<vector> |
| 22 | +#include<algorithm> |
| 23 | + |
| 24 | +usingnamespacestd; |
| 25 | + |
| 26 | +classSolution { |
| 27 | +public: |
| 28 | +intcherryPickup(vector<vector<int>>& grid) { |
| 29 | +int rows = grid.size(); |
| 30 | +int cols = grid[0].size(); |
| 31 | + |
| 32 | + vector<vector<vector<int>>>dp(rows, vector<vector<int>>(cols, vector<int>(cols,0))); |
| 33 | + |
| 34 | +for (int i = rows -1; i >=0; --i) { |
| 35 | +for (int j =0; j < cols; ++j) { |
| 36 | +for (int k =0; k < cols; ++k) { |
| 37 | +int cherries = grid[i][j] + (j != k ? grid[i][k] :0); |
| 38 | +if (i == rows -1) { |
| 39 | + dp[i][j][k] = cherries; |
| 40 | + }else { |
| 41 | +int maxCherries =0; |
| 42 | +for (int dj = -1; dj <=1; ++dj) { |
| 43 | +for (int dk = -1; dk <=1; ++dk) { |
| 44 | +int nj = j + dj; |
| 45 | +int nk = k + dk; |
| 46 | +if (nj >=0 && nj < cols && nk >=0 && nk < cols) { |
| 47 | + maxCherries =max(maxCherries, dp[i +1][nj][nk]); |
| 48 | + } |
| 49 | + } |
| 50 | + } |
| 51 | + dp[i][j][k] = cherries + maxCherries; |
| 52 | + } |
| 53 | + } |
| 54 | + } |
| 55 | + } |
| 56 | + |
| 57 | +return dp[0][0][cols -1]; |
| 58 | + } |
| 59 | +}; |