This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

In a N x N `grid`

representing a field of cherries, each cell is one of three possible integers.

Your task is to collect maximum number of cherries possible by following the rules below:

**Example 1:**

Input:grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]Output:5Explanation: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`

.`grid[i][j]`

is an integer in the set `{-1, 0, 1}`

.b'

\n#### Approach #1: Greedy [Wrong Answer]

\n\n

\n#### Approach #2: Dynamic Programming (Top Down) [Accepted]

\n

\n#### Approach #3: Dynamic Programming (Bottom Up) [Accepted]

\n

\n\n

'
\n\n

\n**Intuition**

Let\'s find the most cherries we can pick up with one path, pick them up, then find the most cherries we can pick up with a second path on the remaining field.

\nThough a counter example might be hard to think of, this approach fails to find the best answer to this case:

\n11100\n00101\n10100\n00100\n00111\n

**Algorithm**

We can use dynamic programming to find the most number of cherries `dp[i][j]`

that can be picked up from any location `(i, j)`

to the bottom right corner. This is a classic question very similar to Minimum Path Sum, refer to the link if you are not familiar with this type of question.

After, we can find an first path that maximizes the number of cherries taken by using our completed `dp`

as an oracle for deciding where to move. We\'ll choose the move that allows us to pick up more cherries (based on comparing `dp[i+1][j]`

and `dp[i][j+1]`

).

After taking the cherries from that path (and removing it from the grid), we\'ll take the cherries again.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`grid`

. Our dynamic programming consists of two for-loops of length`N`

. \n - \n
Space Complexity: , the size of

\n`dp`

. \n

\n

**Intuition**

Instead of walking from end to beginning, let\'s reverse the second leg of the path, so we are only considering two paths from the beginning to the end.

\nNotice after `t`

steps, each position `(r, c)`

we could be, is on the line `r + c = t`

. So if we have two people at positions `(r1, c1)`

and `(r2, c2)`

, then `r2 = r1 + c1 - c2`

. That means the variables `r1, c1, c2`

uniquely determine 2 people who have walked the same `r1 + c1`

number of steps. This sets us up for dynamic programming quite nicely.

**Algorithm**

Let `dp[r1][c1][c2]`

be the most number of cherries obtained by two people starting at `(r1, c1)`

and `(r2, c2)`

and walking towards `(N-1, N-1)`

picking up cherries, where `r2 = r1+c1-c2`

.

If `grid[r1][c1]`

and `grid[r2][c2]`

are not thorns, then the value of `dp[r1][c1][c2]`

is `(grid[r1][c1] + grid[r2][c2])`

, plus the maximum of `dp[r1+1][c1][c2]`

, `dp[r1][c1+1][c2]`

, `dp[r1+1][c1][c2+1]`

, `dp[r1][c1+1][c2+1]`

as appropriate. We should also be careful to not double count in case `(r1, c1) == (r2, c2)`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`grid`

. Our dynamic programming has states. \n - \n
Space Complexity: , the size of

\n`memo`

. \n

\n

**Intuition**

Like in *Approach #2*, we have the idea of dynamic programming.

Say `r1 + c1 = t`

is the `t`

-th layer. Since our recursion only references the next layer, we only need to keep two layers in memory at a time.

**Algorithm**

At time `t`

, let `dp[c1][c2]`

be the most cherries that we can pick up for two people going from `(0, 0)`

to `(r1, c1)`

and `(0, 0)`

to `(r2, c2)`

, where `r1 = t-c1, r2 = t-c2`

. Our dynamic program proceeds similarly to *Approach #2*.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`grid`

. We have three for-loops of size . \n - \n
Space Complexity: , the sizes of

\n`dp`

and`dp2`

. \n

\n\n