Cherry Pickup - Video Solutions

Problem Overview: You are given an n x n grid where cells contain cherries (1), empty spaces (0), or thorns (-1). Starting at (0,0), you must reach (n-1,n-1) and then return to the start. Each cherry can only be collected once and cells with -1 cannot be visited. The goal is to maximize the total cherries collected across both trips.

A direct simulation of going forward and then returning leads to complicated state management. The key insight is that the forward and backward trips can be modeled as two people walking from the start to the end at the same time. Both take the same number of steps k, and their positions determine which cherries are collected.

Approach 1: Dynamic Programming with 3D DP Table (Time: O(n^3), Space: O(n^3))

This approach models the two simultaneous walkers using dynamic programming. Let dp[k][i1][i2] represent the maximum cherries collected after k steps when the first person is at (i1, j1) and the second at (i2, j2). Because both walkers take the same number of steps, j1 = k - i1 and j2 = k - i2. For each step, evaluate four possible transitions: both move right, both move down, or one moves right while the other moves down. If either position hits a thorn, the state is invalid. When both walkers land on the same cell, count the cherry only once.

The DP iterates over steps from 0 to 2n-2, computing the best value from previous states. This transforms the round-trip path problem into a single synchronized traversal problem. The algorithm uses dynamic programming across a matrix grid, tracking all valid combinations of row positions.

Approach 2: Dynamic Programming with Space Optimization (Time: O(n^3), Space: O(n^2))

The 3D DP table stores states for every step, but only the previous step is needed to compute the next one. Replace the full dp[k][i1][i2] structure with two 2D arrays: one for the current step and one for the previous step. During each iteration over k, update the new matrix using values from the previous matrix and then swap references.

This reduces memory from O(n^3) to O(n^2) while keeping the same transitions and logic. The time complexity remains cubic because you still iterate through all valid combinations of i1 and i2 for each step. This version is typically preferred in production code or memory-constrained environments. The technique is common in array and DP problems where state transitions depend only on the previous iteration.

Recommended for interviews: Interviewers usually expect the 3D DP formulation because it demonstrates the key insight of converting the round trip into two synchronized paths. Explaining the state definition and transitions clearly shows strong dynamic programming skills. Implementing the space-optimized version afterward highlights deeper understanding of DP state compression.