This was a very clever 2dimensional 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 ki and kj 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 underestimate 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 ki and kj. 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 klength paths can pickup.
// The two klength 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 (n1, n1).
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 passthrough
continue;
}
int cherries = dp[i, j]; // # of cherries picked up by the two (k1)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, kj).
if (cherries < 0) continue;
// Pickup cherries at (i, k  i) and (j, k j ) if i != j.
// Otherwise, pickup (i, ki).
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);
}
}