C# solution based on StoryPKU's C++ DP Solution

• This was a very clever 2-dimensional DP solution. I converted it to C# from StoryPKU's post. I have the complexity ~ O(N^3) k, i, j. It is polynomial time, at least, and is decent for small n.
This is actually a very complicated, but concise, DP solution.

The algorithm goes something like this:

• Initialize DP to -1

• Set value @ (0,0) equal to input's (0,0) value

• Set maximum path length twice the maximum path length so that two full paths along k - i and k - j respectively can be developed

• For each path of length k create a new DP using the results from the previous DP

• Explore all possibilities of paths k-i and k-j taking the maximum value and storing it in new DP[i,j] for each i,j <= k
• Prior to iterating to next path of length k, set previous DP to current DP
• Return max of DPn and 0

Interesting notes:

• Don't under-estimate the importance of prefilling the DP array with -1. This allows us to determine when we are blocked completely on a given path of length k versus a path that isn't blocked but just doesn't have any cherries (cherries = 0).

• Pay attention to the recurrence relation between i,j and k-i and k-j. Can you explain it?

• Nice try StoryPKU on trying to make it intuitive, but I believe the intuition is still lying with you on this one :-) It is definitely a brilliant solution (just no so much intuitive).

`````` public class Solution
{
private void Fill(int[,] source, int n, int value)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
source[i, j] = value;
}
}
}

public int CherryPickup(int[,] grid)
{
int n = grid.GetUpperBound(0) + 1;
// dp holds maximum # of cherries two k-length paths can pickup.
// The two k-length paths arrive at (i, k - i) and (j, k - j),
// respectively.
int[,] dp = new int[n, n];//Initial DP

Fill(dp, n, -1);

dp[0, 0] = grid[0, 0]; // length k = 0

// maxK: number of steps from (0, 0) to (n-1, n-1).
int maxK = (n - 1) << 1;

for (int k = 1; k <= maxK; k++)
{ // for every path k
int[,] curr = new int[n, n];//Create a DP for this path

Fill(curr, n, -1);

// one path of length k arrive at (i, k - i)
for (int i = 0; i < n && i <= k; i++)
{
// another path of length k arrive at (j, k - j)
for (int j = 0; j < n && j <= k; j++)
{

if ((k - i < n && grid[i, k - i] < 0) || (k - j < n && grid[j, k - j] < 0))
{ // both paths needs to be able to pass-through
continue;
}

int cherries = dp[i, j]; // # of cherries picked up by the two (k-1)-length paths.
// See the figure below for an intuitive understanding

if (i > 0 && j > 0)
{
cherries = Math.Max(cherries, dp[i - 1, j - 1]);
}
if (i > 0)
{
cherries = Math.Max(cherries, dp[i - 1, j]);
}
if (j > 0)
{
cherries = Math.Max(cherries, dp[i, j - 1]);
}

// No viable way to arrive at (i, k - i)-(j, k-j).
if (cherries < 0) continue;

// Pickup cherries at (i, k - i) and (j, k -j ) if i != j.
// Otherwise, pickup (i, k-i).
if (k - i < n)
{
cherries += grid[i, k - i];
}
if(k - j < n)
{
cherries += (i == j ? 0 : grid[j, k - j]);
}

curr[i, j] = cherries;
}
}
dp = curr;//Set previous DP to this DP
}

return Math.Max(dp[n - 1, n - 1], 0);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.