Cherry pickup algorithm
An indepth look at the Cherry Pickup problem on Leetcode.com.
One of the harder questions on Leetcode.com is the Cherry Pickup. I hope this post shines a light on this problem for many people struggling with the solution.
Problem description by Leetcode.com
The problem as described by Leetcode is as follows:
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 (N1, N1) by moving right or down through valid path cells (cells with value 0 or 1);
 After reaching (N1, N1), 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 (N1, N1), then no cherries can be collected.
Symbols we will use to describe the problem
This post aims to simplify the problem and we will be using different symbols. These are outlined below.
 [[],[]] / Matrix of matrixes  Field of cherries
 1  π  Cherry
 0  No cherry (possibly already collected)
 1  α¦ (thorn that blocks the cherry collector)

πΆ  Cherry collector
 Can one make one roundtrip collection
 Can only move down or right on his way to x=N1, y=N1
 Can only move up or left on his way to x=0, y=0
Quiz
A few quiz questions below will help to understand the problem by example.
Question 1 What is the maximum number of cherries, the collector can collect in the following field?
[[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, 0, 0]]
Answer = none because he can never reach his target.
Question 2 What about for this field?
[[0, 0, 0, 0, 0, π],
[π, α¦, 0, 0, 0, 0],
[π, π, π, 0, 0, 0],
[π, α¦, 0, 0, 0, 0],
[π, α¦, 0, 0, π, 0],
[π, 0, 0, 0, 0, 0]]
Lets find out!
//On the way down  5 cherries
[[πΆ, 0, 0, 0, 0, π],
[πΆ, α¦, 0, 0, 0, 0],
[πΆ, π, π, 0, 0, 0],
[πΆ, α¦, 0, 0, 0, 0],
[πΆ, α¦, 0, 0, π, 0],
[πΆ, πΆ, πΆ, πΆ, πΆ, πΆ]]
//Return journey  3 cherries
[[πΆ, 0, 0, 0, 0, π],
[πΆ, α¦, 0, 0, 0, 0],
[πΆ, πΆ, πΆ, πΆ, 0, 0],
[0, α¦, 0, πΆ, 0, 0],
[0, α¦, 0, 0, πΆ, 0],
[0, 0, 0, 0, 0, πΆ]]
Answer = 8
Notice one cherry is still left in the field, in the top right corner. Picking up that cherry would have meant leaving more cherries unpicked in the field. The reason we cannot possibly pick up all of the cherries in the field is because we can only move in down/right on the way down, then up/left on the return journey. We can only make one roundtrip cherry collection.
Let us think about this further and come up with some other truths that may later help us, before writing any code
 Cherries can only be picked up once. They are gone once picked up
 You cannot hit a thorn and continue. You must avoid thorns
 You may cross over a path you have already traveled. Sometimes this is wise to avoid thorns and get to other cherries

Every path that can be traveled by going up/left from the destination (N1, N1) can also be identically traveled by going down and right from the origin (0,0).
 Optimization alert. Therefore two people traveling down/right βone wayβ can make the same cherry pickups as one person doing a βroundtrip.β
Source code
Source code in JavaScript for working out the max number of cherries you can pick up with two people, starting at the origin 0,0 and ending at the destination N1, N1 both with the restriction of only being able to move down or right.

The recursion ensures that we explore all viable paths

The Math.max ensures that we choose the two most lucrative paths
var cherryPickup = function (grid) {
var maxY = grid.length;
var maxX = grid[0].length;
var memo = {};
function dp(yPersonA, xPersonA, xPersonB) {
//work out corrosponding Y variable for personB. (works since personA and personB have made the same number of moves)
var yPersonB = yPersonA + xPersonA  xPersonB;
//key for the current state
var memoKey = yPersonA + "_" + xPersonA + "_" + xPersonB;
//work out if we are out of bounds
var overTheEdge = maxY == yPersonA  maxY == yPersonB  maxX == xPersonA  maxX == xPersonB; //we are actually over the edge HERE!!
if (overTheEdge) {
return 999999;
}
var personAHitAThorn = grid[yPersonA][xPersonA] == 1;
var personBHitAThorn = grid[yPersonB][xPersonB] == 1;
if (personAHitAThorn  personBHitAThorn) {
//impossible move, either over the edge or directly on a thorn
return 999999;
} else if (yPersonA == maxY  1 && xPersonA == maxX  1) {
//reached the target finally
return grid[yPersonA][xPersonA];
} else if (memo[memoKey] !== undefined) {
//already visited
return memo[memoKey];
} else {
var personAHasCherry = grid[yPersonA][xPersonA] === 1;
var personBHasCherry =
yPersonB !== yPersonA && xPersonB !== xPersonA && //if personA didn't take it first!
grid[yPersonB][xPersonB] === 1;
var cherriesCollectedByBothPeopleThisTurn =
(personAHasCherry ? 1 : 0) +
(personBHasCherry ? 1 : 0);
//both people make all possible single moves they can make (down and right)
//personB by definition will likely always be on a different path than personA since:
// * it will generate more COMBINED cherries (see above cherriesCollectedByBothPeopleThisTurn)
var maxCherriesCollectedByBothPeopleForRemainingTurns = Math.max(
Math.max(
dp(yPersonA, xPersonA + 1, xPersonB + 1), //personA right personB right
dp(yPersonA + 1, xPersonA, xPersonB + 1)), //personA down personB right
Math.max(
dp(yPersonA, xPersonA + 1, xPersonB), //personA right personB down
dp(yPersonA + 1, xPersonA, xPersonB)) //personA down personB down
);
var cherriesCollectedRecursive = cherriesCollectedByBothPeopleThisTurn + maxCherriesCollectedByBothPeopleForRemainingTurns;
memo[memoKey] = cherriesCollectedRecursive;
return cherriesCollectedRecursive;
}
}
return Math.max(0, dp(0, 0, 0));
}