Two Drones, One Harvest

Hard2-D Dynamic Programming

Problem

An orchard is a grid crops, where crops[r][c] is the amount of fruit (a non-negative integer) on cell (r, c). Two harvest drones both start at the top-left cell and both fly to the bottom-right cell, each moving only right or down.

A drone harvests every cell it visits, but a cell's fruit can only be collected once: if both drones pass over the same cell, it counts once. Return the maximum total fruit the two drones can collect together.

Example 1

Input:
crops = [[1, 5, 0], [2, 0, 4], [0, 3, 1]]
Output:
16

One drone flies along the top row and down the right edge (1, 5, 0, 4, 1); the other goes down the left edge and along the bottom (2, 0, 3). Together they collect every non-zero cell: 16.

Example 2

Input:
crops = [[3, 1, 2, 6]]
Output:
12

With a single row both drones take the same path, so each cell is counted once.

Constraints

  • 1 ≤ crops.length, crops[0].length ≤ 50
  • 0 ≤ crops[r][c] ≤ 100

Hint

Show the first hint

Running the single-drone DP twice (best path, wipe its cells, best path again) is not optimal. You must plan both drones together.

Walkthrough

How to approach it

01Clarify before coding

  • If both drones visit the same cell, is it counted once? Yes.
  • Are there blocked cells? No, every cell is open, so a valid plan always exists.
  • Can the drones take the same full path? Yes, then the answer is just one path's total.

02Brute force

Enumerate every pair of right/down paths and sum the union of their cells. A tempting shortcut, greedily taking the best single path and then the best path on what is left, is wrong.

Cost: Pairs of paths: C(m + n - 2, m - 1)² is astronomically large; the greedy shortcut is fast but gives wrong answers (the first drone can ruin the second's options).

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.