Problem Statement
Cherry Pickup
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
0means the cell is empty.1means the cell contains a cherry that you can pick up and pass through.-1means the cell contains a thorn that blocks your way.
Return the maximum number of cherries you can collect by following the rules below:
- Starting at the position
(0, 0)and reaching(n - 1, n - 1)by moving right or down through valid path cells (cells with value 0 or 1). - After reaching
(n - 1, n - 1), returning to(0, 0)by moving left or up through valid path cells. - When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell
0. - If there is no valid path between
(0, 0)and(n - 1, n - 1), then no cherries can be collected.
Examples
Example 1:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.
Example 2:
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Explanation: There is no path from (0, 0) to (2, 2) that avoids the thorns.
Constraints
- n == grid.length
- n == grid[i].length
- 1 <= n <= 50
- -1 <= grid[i][j] <= 1
Problem Breakdown
To solve this problem, we need to:
- This problem can be solved using dynamic programming.
- Instead of thinking about a forward trip followed by a backward trip, we can think of it as two people starting from (0, 0) and both reaching (n-1, n-1).
- At each step, both people can move either right or down, and we need to maximize the total number of cherries they collect.
- If both people are at the same cell, we should count the cherry only once.
- We can use a 4D DP array dp[r1][c1][r2][c2] to represent the maximum cherries that can be collected when person 1 is at (r1, c1) and person 2 is at (r2, c2).
- We can optimize the space by observing that r1 + c1 = r2 + c2 (both people take the same number of steps), so we can use a 3D DP array dp[r1][c1][r2].
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Cherry Pickup
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
0means the cell is empty.1means the cell contains a cherry that you can pick up and pass through.-1means the cell contains a thorn that blocks your way.
Return the maximum number of cherries you can collect by following the rules below:
- Starting at the position
(0, 0)and reaching(n - 1, n - 1)by moving right or down through valid path cells (cells with value 0 or 1). - After reaching
(n - 1, n - 1), returning to(0, 0)by moving left or up through valid path cells. - When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell
0. - If there is no valid path between
(0, 0)and(n - 1, n - 1), then no cherries can be collected.
Examples
Example 1:
The player started at (0, 0) and went down, down, right right to reach (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left to return home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.
Example 2:
There is no path from (0, 0) to (2, 2) that avoids the thorns.
Problem Breakdown
Constraints:
- n == grid.length
- n == grid[i].length
- 1 <= n <= 50
- -1 <= grid[i][j] <= 1
Key Insights:
This problem can be solved using dynamic programming.
Instead of thinking about a forward trip followed by a backward trip, we can think of it as two people starting from (0, 0) and both reaching (n-1, n-1).
At each step, both people can move either right or down, and we need to maximize the total number of cherries they collect.
If both people are at the same cell, we should count the cherry only once.
We can use a 4D DP array dp[r1][c1][r2][c2] to represent the maximum cherries that can be collected when person 1 is at (r1, c1) and person 2 is at (r2, c2).
We can optimize the space by observing that r1 + c1 = r2 + c2 (both people take the same number of steps), so we can use a 3D DP array dp[r1][c1][r2].
Real-World Application
This problem has several practical applications:
Resource Collection
Optimizing the collection of resources in a grid-based environment, such as robots collecting items in a warehouse.
Path Planning
Planning optimal paths for multiple agents in a shared environment, ensuring they don't interfere with each other.
Coordination Problems
Solving coordination problems where multiple agents need to work together to achieve a common goal.