LeetCode 1463 - Cherry Pickup II

Here is a complete, detailed technical solution guide for LeetCode 1463 - Cherry Pickup II following your formatting req

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 1463

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Here is a complete, detailed technical solution guide for LeetCode 1463 - Cherry Pickup II following your formatting requirements.

Problem Understanding

The problem gives us a rows x cols grid representing a field of cherries. Each cell contains a non-negative integer indicating the number of cherries at that location. Two robots start at the top-left (0, 0) and top-right (0, cols - 1) corners, and both must reach the bottom row of the grid. Robots can move diagonally left, straight down, or diagonally right at each step. When a robot visits a cell, it collects all cherries there; if both robots land on the same cell, only one collects the cherries.

The input is a 2D list of integers grid, with constraints 2 <= rows, cols <= 70 and 0 <= grid[i][j] <= 100. The output is the maximum total cherries collected by both robots following the movement rules.

Important edge cases include: grids with minimal size (2x2), grids with all zeros, robots landing on the same cell frequently, and grids with maximum cherries at different locations forcing non-overlapping paths.

The problem requires an efficient solution because a brute-force exploration of all possible paths for both robots would be exponential in rows * cols and infeasible given the constraints.

Approaches

Brute Force Approach:

The naive approach is to try all possible paths for both robots recursively. At each row, for robot 1 and robot 2, we consider three moves (left-diagonal, down, right-diagonal) and recurse until reaching the last row. At each step, we sum the cherries collected by both robots, avoiding double-counting if they occupy the same cell.

This approach is correct, as it explores all combinations, but it is extremely slow. With cols columns and rows rows, the number of possible states is roughly O(3^rows * 3^rows) = O(9^rows), which is exponential and infeasible for rows up to 70.

Optimal Approach (Dynamic Programming):

Key insight: the problem has overlapping subproblems. The maximum cherries collected from row i onward depends only on the current positions of both robots in row i. Therefore, we can define a DP state dp[i][j1][j2] representing the maximum cherries collected from row i to the bottom when robot 1 is at column j1 and robot 2 is at column j2.

Transition: from dp[i][j1][j2], consider all 9 possible next moves (j1-1, j1, j1+1 × j2-1, j2, j2+1) to dp[i+1][new_j1][new_j2]. Add cherries from the current row (taking care to only count once if j1 == j2). The final answer is dp[0][0][cols-1].

This DP reduces complexity from exponential to O(rows * cols * cols * 9) = O(rows * cols^2) with memoization.

Approach Time Complexity Space Complexity Notes
Brute Force O(9^rows) O(rows) Recursively try all robot moves, too slow
Optimal (DP) O(rows * cols^2) O(rows * cols^2) Memoized recursion or 3D DP, feasible for rows, cols ≤ 70

Algorithm Walkthrough

  1. Define DP State: Let dp[i][j1][j2] be the maximum cherries collected from row i to the bottom if robot 1 is at column j1 and robot 2 at column j2.
  2. Base Case: If i == rows, return 0. Robots are past the last row, so no cherries remain.
  3. Current Cherries: For positions (i, j1) and (i, j2), collect grid[i][j1] + grid[i][j2] if j1 != j2; otherwise, only grid[i][j1].
  4. Recursion / Transition: Iterate dj1 and dj2 over [-1, 0, 1] representing left, down, and right moves. For each valid (new_j1, new_j2) in bounds, recursively compute dp[i+1][new_j1][new_j2].
  5. Memoization: Store results in a 3D table to avoid recomputation.
  6. Return: Start recursion at dp[0][0][cols-1], which represents the top-left and top-right starting positions.

Why it works: Each state dp[i][j1][j2] correctly represents the optimal cherries collectable from that row onward given the robots' positions. By exploring all 9 moves per step and storing results, the DP ensures that no subproblem is solved twice and all combinations are considered. This guarantees an optimal solution.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        @lru_cache(maxsize=None)
        def dp(i: int, j1: int, j2: int) -> int:
            if j1 < 0 or j1 >= cols or j2 < 0 or j2 >= cols:
                return float('-inf')  # invalid position

            # Cherries collected at current positions
            result = grid[i][j1]
            if j1 != j2:
                result += grid[i][j2]

            if i == rows - 1:  # last row
                return result

            # Recurse for all 9 possible next moves
            max_cherries = float('-inf')
            for dj1 in [-1, 0, 1]:
                for dj2 in [-1, 0, 1]:
                    max_cherries = max(max_cherries, dp(i + 1, j1 + dj1, j2 + dj2))

            result += max_cherries
            return result

        return dp(0, 0, cols - 1)

Explanation: We use lru_cache to memoize dp(i, j1, j2) results. At each step, we check bounds, compute cherries collected, and recursively explore all 9 moves. The recursion builds up the maximum cherries collected from the bottom row backward.

Go Solution

func cherryPickup(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	memo := make([][][]int, rows)
	for i := 0; i < rows; i++ {
		memo[i] = make([][]int, cols)
		for j := 0; j < cols; j++ {
			memo[i][j] = make([]int, cols)
			for k := 0; k < cols; k++ {
				memo[i][j][k] = -1
			}
		}
	}

	var dp func(i, j1, j2 int) int
	dp = func(i, j1, j2 int) int {
		if j1 < 0 || j1 >= cols || j2 < 0 || j2 >= cols {
			return -1 << 60
		}
		if memo[i][j1][j2] != -1 {
			return memo[i][j1][j2]
		}

		result := grid[i][j1]
		if j1 != j2 {
			result += grid[i][j2]
		}

		if i == rows-1 {
			memo[i][j1][j2] = result
			return result
		}

		maxCherries := -1 << 60
		for dj1 := -1; dj1 <= 1; dj1++ {
			for dj2 := -1; dj2 <= 1; dj2++ {
				next := dp(i+1, j1+dj1, j2+dj2)
				if next > maxCherries {
					maxCherries = next
				}
			}
		}

		result += maxCherries
		memo[i][j1][j2] = result
		return result
	}

	return dp(0, 0, cols-1)
}

Go-specific notes: We preallocate a 3D memo slice and use -1 as the uninitialized marker. Go requires explicit integer overflow-safe initialization (-1 << 60) for negative infinity.

Worked Examples

Example 1:

grid = [[3,1,1],
        [2,5,1],
        [1,5,5],
        [2,1,1]]

Step tracing for DP:

Row Robot1 Robot2 Cherries collected this step Cumulative max
0 0 2 3 + 1 = 4 4
1 0 1 2 + 5 = 7 11
2 1 2