Solution: Cherry Pickup

Explore a dynamic programming solution that models the Cherry Pickup problem as two synchronized paths. Learn to use a 3D memoization table to track maximum cherries collected while navigating an n by n grid with obstacles. Understand the approach to optimize both forward and return trips efficiently in C++.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given an $n \times n$ grid representing a field of cherries. Each cell in the grid can have one of three possible values:

$0$ : An empty cell that can be walked through
$1$ : A cell containing a cherry that can be picked and then passed through
$-1$ : A cell containing a thorn, which cannot be crossed

Your task is to find the maximum number of cherries that can be collected while following these rules:

Start at the top-left corner $(0,0)$ and reach the bottom-right corner $(n-1,~n-1)$ by only moving right or down through valid cells ( $0$ or $1$ ).
After reaching the bottom-right corner, return to the starting point $(0, 0)$ ...