Two Collectors Descending
Two collectors start on the top row, the first in the leftmost column and the second in the rightmost. Each turn BOTH move down one row, and each may shift to the column directly below, one to the left, or one to the right, without leaving the grid.
A collector takes the value of the cell it lands on. If both land on the SAME cell, that value is taken only once. Print the largest total they can gather, counting the two starting cells.
3 1 1
2 5 1 -> 24
1 5 5
2 1 1
## Why one collector at a time fails
Running the best single path, removing it, then running the best path again is the obvious reduction and it is wrong. The first collector, choosing greedily for itself, can take a cell that was the only way for the second to reach a much richer region.
The two routes have to be chosen TOGETHER, which means the state must describe both.
## The state
Both collectors are always on the same row, because they move in lockstep. So the state is that row plus the two columns:
dp[r][c1][c2] = the most collected through row r, with the collectors in columns c1 and c2
The shared row is what keeps this three-dimensional rather than four. Recognising that a synchronising constraint removes a dimension is the reusable part, and it is the same observation that made problem 488 need only two dimensions for three groups.
## The transition
From (c1, c2) there are nine moves, three for each collector:
for d1 in -1, 0, 1:
for d2 in -1, 0, 1:
n1, n2 = c1 + d1, c2 + d2
if both in range:
gain = g[r][n1] + (g[r][n2] if n1 != n2 else 0)
relax dp[r][n1][n2] with dp[r-1][c1][c2] + gain
## The same-cell rule
When n1 == n2 the value counts ONCE. Adding it twice is the single most common bug and it
inflates the answer whenever the two best routes want to converge.
9 9 / 9 9 answers 36, not 45: on each row the two collectors sit in different columns and
collect 18, twice. And a one-column grid 1 answers 1, because both collectors start on the
same cell and it is counted once.
Those two inputs bracket the rule from both sides.
## Reading the answer
Take the maximum over ALL pairs of final columns, not dp[m-1][0][n-1]. The collectors end
wherever is best, and there is no reason for them to return to their starting columns.
## Boundaries
A single row means no moves at all, so the answer is just the two starting cells, counted
once if they coincide. 1 2 3 answers 4, taking the 1 and the 3 and never the 2.
## Cost
Time O(m n^2) with nine transitions each. Space O(n^2) with two layers.