The idea
Two walkers on a grid, two mines receiving food, two pointers in two strings: the decision at each step depends on where every one of them stands, so the state must describe them together.
Then trim what is implied. Two paths that take the same number of steps share the step count, so (step, row1, row2) replaces four coordinates.
Keep only what the future can depend on. Two robots walking down a grid together need the current row and their two columns; how they got there no longer matters.
Sample problem
1463. Cherry Pickup II ↗ Hard
Two robots start in the top-left and top-right corners of a grid of cherries. Each step both move down one row, to the column below-left, below or below-right. A cell’s cherries are collected once. Return the most cherries they can collect together.
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]] output = 24
Why the solution works
Planning one robot and then the other fails: the best path for the first can steal cherries the pair would have shared better. The two robots must be decided together.
They always stand in the same row, so the state is (row, column of robot 1, column of robot 2). One row number serves both, which is what keeps the table small.
From each state there are 3 × 3 joint moves. Filling the rows from the bottom up, each entry adds the cherries under the robots to the best entry reachable in the row below.
Complexity: O(R · C² · 9) time, O(C²) memory since only two rows of the table are kept.
Watch out
- A full table over every step may not fit in memory: keep only the current and next layer.
- Mark unreachable states so they are never extended.
- If two orderings describe the same situation, count or store it once.