Find the Maximum Number of Fruits Collected - Solution & Explanation

Problem Overview: You are given a matrix where each cell contains a certain number of fruits. Multiple collectors move through the grid simultaneously and gather fruits along their paths. When two collectors land on the same cell, the fruit should only be counted once. The goal is to compute the maximum total fruits that can be collected following the allowed movements.

Approach 1: Recursive DFS with Memoization (Time: O(m * n^2), Space: O(m * n^2))

This approach models the problem as a recursive search where the state represents the row index and the column positions of the collectors. At each step, both collectors move to the next row with possible column shifts (left, stay, right). The recursive function explores all combinations of moves and collects fruits from the current cells. A memoization table caches results for states like (row, col1, col2) so the same subproblem is not recomputed. This drastically reduces exponential branching to polynomial complexity. DFS with memoization is intuitive when you first reason about the transitions and want a clear top‑down formulation.

Approach 2: Dynamic Programming with Three-Dimensional DP Array (Time: O(m * n^2), Space: O(m * n^2))

The optimal approach converts the recursive idea into bottom‑up dynamic programming. Define dp[row][c1][c2] as the maximum fruits collected when both collectors are on row row at columns c1 and c2. For every state, iterate through the nine possible column transitions for the next row (each collector can move left, stay, or right). Add fruits from the current cells, making sure not to double count when c1 == c2. The DP table is filled row by row until the last row is processed. This eliminates recursion overhead and gives a predictable iteration pattern, which performs well in practice for large grids.

Both approaches rely on the same insight: the future result depends only on the current row and the column positions of both collectors. That makes the problem a classic multi‑agent grid DP similar to problems in Dynamic Programming on a Matrix. The DP state captures both positions simultaneously, which is why a three‑dimensional structure is required.

Recommended for interviews: The three‑dimensional DP solution is what interviewers usually expect. Start by describing the recursive state and transitions, then convert it to a bottom‑up DP table. Mentioning the memoized DFS first shows you understand the problem decomposition, while presenting the iterative DP demonstrates strong command of Array and grid dynamic programming techniques.