Cherry pickup II
GoogleThe problem
Given a n x m 2d integer array called matrix where matrix[i][j] represents the number of cherries you can pick up from the (i, j) cell.Given two robots that can collect cherries, one is located at the top-leftmost (0, 0) cell and the other at the top-rightmost (0, m-1) cell.
Return the** maximum** number of cherries that can be picked by the two robots in total, following these rules:
-
Robots that are standing on (i, j) cell can only move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1), if it exists in the matrix.
-
A robot will pick up all the cherries in a given cell when it passes through that cell.
-
If both robots come to the same cell at the same time, only one robot takes the cherries.
-
Both robots must reach the bottom row in matrix.
Input: matrix = [[2, 1, 3], [4, 2, 5], [1, 6, 2], [7, 2, 8]] Output: 37 Explanation: Possible left robot path:- Start at 0th cell (2) -> down (4) -> down-right (6) ->down-left (7) Possible right robot path:- Start at 2nd cell (3) -> down (5) -> down (2) -> down (8)
Input: matrix = [[1, 4, 4, 1], [1, 2, 2, 1], [5, 6, 10, 11], [8, 1, 1, 1]] Output: 32 Explanation: Possible left robot path:- Start at 0th cell (1) -> down-right (2) -> down (6) ->down-left (8) Possible right robot path:- Start at 3rd cell (1) -> down-left (2) -> down-right (11) -> down (1)
Input: matrix = [[1, 2, 3], [5, 4, 6], [4, 4, 1]]
- n == number of rows in matrix
- m == number of columns in matrix
- 2 <= n, m <= 70
- 0 <= matrix[i][j] <= 1000
cpp
class Solution {
public:
int cherryPickup(vector<vector<int>>& matrix) {
}
};java
class Solution {
public int cherryPickup(int[][] matrix) {
}
}python
class Solution:
def cherryPickup(self, matrix):javascript
class Solution {
cherryPickup(matrix) {
}
}csharp
public class Solution
{
public int CherryPickup(int[][] matrix)
{
}
}go
func cherryPickup(matrix [][]int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01State is row r and the two robots' columns c1 and c2.
- 02Add both cells' cherries, counting once when columns match.
- 03Try all nine pairs of next-column moves.
- 04Memoize or bottom-up compute from the final row.
Reference answer
Then expect these follow-ups
How would you reconstruct both robots' paths?
Tests: DP reconstruction
How would you reduce bottom-up memory?
Tests: rolling arrays
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question