> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/741.-cherry-pickup.md).

# 741. Cherry Pickup

https\://leetcode.com/problems/cherry-pickup/

In a N x N `grid` representing a field of cherries, each cell is one of three possible integers.

* 0 means the cell is empty, so you can pass through;
* 1 means the cell contains a cherry, that you can pick up and pass through;
* -1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible 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.

**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.
```

**Note:**

* `grid` is an `N` by `N` 2D array, with `1 <= N <= 50`.
* Each `grid[i][j]` is an integer in the set `{-1, 0, 1}`.
* It is guaranteed that grid\[0]\[0] and grid\[N-1]\[N-1] are not -1.

N阶方阵上0代表可通过，1代表有果子，-1代表不可通过，从(0, 0)开始可每次向下或向右走到(N - 1, N-1)，再每步向上或向左走回到(0，0)，问最多能拿到多少果子。往回走可以看作是另一条正着走的path。但用两遍max path sum的谈心法是错误的，因为第二遍会取决于第一遍时的结果，而第一遍时最优解不一定是全局最优。既然问题出在了第二遍时丢失了第一遍时的信息，那把两条paths看作是两个人同时独立走，并在它俩相遇时只拿一次果子：把两条paths的位置信息encode进DP状态，就避免了第二条path错误的只关联在第一条path的最优解上。action分别为第一个人下/右与第二个人下右四种，dp\[x1]\[y1]\[x2]表示从(x1, y1, x2, x1 + y1 - x2)出发到(N-1, N-1)能拿到最多果子数。

思路参考自[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/cherry-pickup/discuss/329945/Very-easy-to-follow-%253A-step-by-step-recursive-backtracking-with-memoization-N4)。

```cpp
/*
 * @lc app=leetcode id=741 lang=cpp
 *
 * [741] Cherry Pickup
 */

// @lc code=start
class Solution {
public:
    int N;
    int dfs(vector<vector<int>> &g, vector<vector<vector<int>>> &dp, int x1, int y1, int x2) {
        const int y2 = x1 + y1 - x2;
        if (x1 == N || y1 == N || x2 == N || y2 == N || g[x1][y1] == -1 || g[x2][y2] == -1) return -1; 
        if (dp[x1][y1][x2] != INT_MIN) return dp[x1][y1][x2];
        int res = g[x1][y1];
        if (x1 != x2) res += g[x2][y2];
        if (x1 == N - 1 && y1 == N - 1) return res;
        const auto r = max(dfs(g, dp, x1 + 1, y1, x2 + 1), max(dfs(g, dp, x1, y1 + 1, x2 + 1), max(dfs(g, dp, x1 + 1, y1, x2), dfs(g, dp, x1, y1 + 1, x2))));
        if (r == -1) res = -1;
        else res += r;
        return dp[x1][y1][x2] = res;
    }

    int cherryPickup(vector<vector<int>>& grid) {
        N = grid.size();
        auto dp = vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(N, INT_MIN)));
        return max(0, dfs(grid, dp, 0, 0, 0));
    }
};
// @lc code=end


```