3D DP · Agents, resources, and state machines

Use 3D DP only when three independent facts change future legal moves or value. The main danger is not syntax; it is allowing the product of coordinate sizes to grow without checking it.

Worked model · Two synchronized robots

LeetCode Cherry Pickup II places two robots on the top row. Each moves down-left, down, or down-right.

After row moves, both robots are on that same row. Therefore:

solve(row, c1, c2) = maximum cherries collectable from row onward when robot 1 is at column c1 and robot 2 is at column c2.

Storing (r1, c1, r2, c2) would be a redundant 4D state because r1 == r2.

flowchart TD
  accTitle: Three-dimensional state transition for two grid robots
  accDescr: A state contains the common row and both robot columns. Add the cherries at both cells, counting once when the columns match, then try all nine pairs of horizontal moves to the next row and keep the best suffix.
  A["state (row, c1, c2)"] --> B["gain grid[row][c1]"]
  B --> C{"c1 equals c2?"}
  C -->|no| D["+ grid[row][c2]"]
  C -->|yes| E["count shared cell once"]
  D --> F["try dc1, dc2 in {-1,0,1}"]
  E --> F
  F --> G["9 next states<br/>(row + 1, c1 + dc1, c2 + dc2)"]
  G --> H["gain + maximum suffix"]

Recurrence

gain(row, c1, c2) =
    grid[row][c1]                              if c1 == c2
    grid[row][c1] + grid[row][c2]             otherwise

solve(row, c1, c2) =
    gain + max solve(row + 1, c1 + d1, c2 + d2)
               for d1,d2 in {-1,0,1}

Out-of-bounds states return negative infinity so they cannot win a maximum. The last row returns its gain with no further move.

Complexity

• states: R × C × C;
• transitions per state: at most 3 × 3 = 9;
• time: O(RC²);
• memo space: O(RC²);
• bottom-up rolling-layer space: O(C²).

PythonC++17C++11

def cherry_pickup_two_robots(grid: list[list[int]]) -> int:
    """Return the maximum cherries collected by two top-to-bottom robots."""
    if not grid or not grid[0]:
        return 0
    columns = len(grid[0])
    if any(len(row) != columns for row in grid):
        raise ValueError("grid must be rectangular")

    @cache
    def solve(row: int, first_column: int, second_column: int) -> int | None:
        if not (0 <= first_column < columns and 0 <= second_column < columns):
            return None  # Invalid moves are absent, not a guessed low score.

        cherries = grid[row][first_column]
        if first_column != second_column:
            cherries += grid[row][second_column]  # Count a shared cell only once.
        if row == len(grid) - 1:
            return cherries

        best_suffix: int | None = None
        for first_step in (-1, 0, 1):
            for second_step in (-1, 0, 1):
                # Both robot positions are required to describe the next state.
                candidate = solve(
                    row + 1,
                    first_column + first_step,
                    second_column + second_step,
                )
                if candidate is not None:
                    best_suffix = (
                        candidate
                        if best_suffix is None
                        else max(best_suffix, candidate)
                    )
        assert best_suffix is not None
        return cherries + best_suffix

    answer = solve(0, 0, columns - 1)
    assert answer is not None
    return answer

inline long long cherry_pickup_two_robots(
    const std::vector<std::vector<int>>& grid) {
  if (grid.empty() || grid.front().empty()) {
    return 0;
  }
  const int rows = static_cast<int>(grid.size());
  const int columns = static_cast<int>(grid.front().size());
  for (const auto& row : grid) {
    if (static_cast<int>(row.size()) != columns) {
      throw std::invalid_argument("grid must be rectangular");
    }
  }

  constexpr long long negative_infinity =
      std::numeric_limits<long long>::lowest() / 4;
  std::vector<std::vector<std::vector<long long>>> memo(
      rows, std::vector<std::vector<long long>>(
                columns, std::vector<long long>(columns, negative_infinity)));
  std::vector<std::vector<std::vector<bool>>> seen(
      rows, std::vector<std::vector<bool>>(
                columns, std::vector<bool>(columns, false)));

  std::function<long long(int, int, int)> solve =
      [&](int row, int first_column, int second_column) -> long long {
    if (first_column < 0 || first_column >= columns ||
        second_column < 0 || second_column >= columns) {
      return negative_infinity;  // Invalid moves must never win a maximum.
    }
    if (seen[row][first_column][second_column]) {
      return memo[row][first_column][second_column];
    }
    seen[row][first_column][second_column] = true;

    long long cherries = grid[row][first_column];
    if (first_column != second_column) {
      cherries += grid[row][second_column];  // Count a shared cell only once.
    }
    if (row == rows - 1) {
      return memo[row][first_column][second_column] = cherries;
    }

    long long best_suffix = negative_infinity;
    for (int first_step = -1; first_step <= 1; ++first_step) {
      for (int second_step = -1; second_step <= 1; ++second_step) {
        // Both robot positions are required to describe the next state.
        best_suffix =
            std::max(best_suffix,
                     solve(row + 1, first_column + first_step,
                           second_column + second_step));
      }
    }
    return memo[row][first_column][second_column] = cherries + best_suffix;
  };

  return solve(0, 0, columns - 1);
}

inline long long cherry_pickup_two_robots(
    const std::vector<std::vector<int>>& grid) {
  if (grid.empty() || grid.front().empty()) {
    return 0;
  }
  const int rows = static_cast<int>(grid.size());
  const int columns = static_cast<int>(grid.front().size());
  for (const auto& row : grid) {
    if (static_cast<int>(row.size()) != columns) {
      throw std::invalid_argument("grid must be rectangular");
    }
  }

  constexpr long long negative_infinity =
      std::numeric_limits<long long>::lowest() / 4;
  std::vector<std::vector<std::vector<long long>>> memo(
      rows, std::vector<std::vector<long long>>(
                columns, std::vector<long long>(columns, negative_infinity)));
  std::vector<std::vector<std::vector<bool>>> seen(
      rows, std::vector<std::vector<bool>>(
                columns, std::vector<bool>(columns, false)));

  std::function<long long(int, int, int)> solve =
      [&](int row, int first_column, int second_column) -> long long {
    if (first_column < 0 || first_column >= columns ||
        second_column < 0 || second_column >= columns) {
      return negative_infinity;  // Invalid moves must never win a maximum.
    }
    if (seen[row][first_column][second_column]) {
      return memo[row][first_column][second_column];
    }
    seen[row][first_column][second_column] = true;

    long long cherries = grid[row][first_column];
    if (first_column != second_column) {
      cherries += grid[row][second_column];  // Count a shared cell only once.
    }
    if (row == rows - 1) {
      return memo[row][first_column][second_column] = cherries;
    }

    long long best_suffix = negative_infinity;
    for (int first_step = -1; first_step <= 1; ++first_step) {
      for (int second_step = -1; second_step <= 1; ++second_step) {
        // Both robot positions are required to describe the next state.
        best_suffix =
            std::max(best_suffix,
                     solve(row + 1, first_column + first_step,
                           second_column + second_step));
      }
    }
    return memo[row][first_column][second_column] = cherries + best_suffix;
  };

  return solve(0, 0, columns - 1);
}

Pattern A · Time × budget × mode

LeetCode Best Time to Buy and Sell Stock IV permits at most k transactions.

One valid contract is:

solve(day, remaining_sales, holding) = maximum future profit from day onward, given whether one share is held.

Decisions:

Mode	Choice	Cash change	Next mode
not holding	skip	0	not holding
not holding	buy	-price[day]	holding
holding	hold	0	holding
holding	sell	+price[day]	not holding, one fewer sale

stateDiagram-v2
  accTitle: Stock dynamic programming as a bounded state machine
  accDescr: On each day, the not-holding state may skip or buy, while the holding state may hold or sell. A sale consumes one transaction from the remaining budget. Every transition advances to the next day.
  state "not holding" as Cash
  state "holding" as Hold
  Cash --> Cash: skip / 0
  Cash --> Hold: buy / -price
  Hold --> Hold: hold / 0
  Hold --> Cash: sell / +price; use one sale

The dimension sizes are n × (k + 1) × 2, so time is O(nk) and the constant mode dimension can be represented by two arrays of length k + 1.

State-definition choice

You may count:

• completed transactions;
• remaining transactions;
• buys used;
• sells used.

Any can work, but transitions and base cases must match exactly. Saying “used transactions” while decrementing it is a semantic bug.

Pattern B · Item × resource A × resource B

Two-budget knapsack might store:

dp[i][a][b] = best value using the first i items within budgets a and b.

The natural complexity is O(items × A × B). If each item is 0/1, both resource loops descend when compressing the item dimension:

for each item (cost_a, cost_b, value):
    for a from A down to cost_a:
        for b from B down to cost_b:
            dp[a][b] = max(dp[a][b],
                           dp[a-cost_a][b-cost_b] + value)

Descending only one resource can still reuse the item through the other axis.

Pattern C · Position × state × remaining changes

Many problems add a bounded exception:

• sequence index;
• current mode/category;
• number of edits or switches remaining.

Examples include changing at most k values, choosing at most k segments, or matching strings with a bounded error budget.

Before adding the third coordinate, ask whether it can be derived:

• if every transition consumes exactly one step, “steps used” may equal index;
• if remaining budget equals total - used, keep one, not both;
• if the mode has only two values, named rolling arrays may be clearer than a literal 3D table.

Memory compression

If every state at layer t reads only layer t + 1 or t - 1, keep two 2D layers.

flowchart LR
  accTitle: Compressing a layered three-dimensional DP
  accDescr: Compute every state in the current two-dimensional layer from the next layer, complete the whole layer, then swap the buffers. Never overwrite a dependency layer while a state can still read it.
  A["next[c1][c2]"] --> B["compute all current[c1][c2]"]
  B --> C["finish entire layer"]
  C --> D["swap current and next"]
  D --> A

Do not compress when:

• transitions read multiple nonadjacent layers;
• reconstruction needs the full predecessor relation;
• in-place update order is not proven;
• the full table already fits and clarity matters more.

3D review checklist

• What does each coordinate represent?
• Can any coordinate be derived from another?
• What is the product of their ranges?
• How many transitions are tried per state?
• Is a dense array realistic, or are reachable states sparse?
• Can one progress layer be rolled safely?

“3D” is not automatically advanced. A precise O(nk × 2) state may be simpler and faster than an unclear 1D recurrence.