DSA Notes

Dynamic Programming

Advanced DP II

When several things move at once, the state holds all of them.

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.
Watch it run

Practise on LeetCode