Chapter 9 · Dynamic programming

Dynamic programming is exhaustive search over a state graph, with each repeated state solved once. The hard part is not filling a table. It is deciding which histories have the same future and may safely share one answer.

The DP recognition test

Ask these questions before writing dp:

1. Choices: can the solution be described as a sequence of decisions?
2. Repeated future: can different decision histories reach the same remaining problem?
3. Complete state: can a small tuple capture everything that changes future legal moves or value?
4. Progress: does every transition move toward a base case?

If the first two answers are yes, memoized search is a strong first model. If each state has only one incoming history, memoization may add no value. If transitions can cycle without a decreasing resource, model a graph algorithm instead of forcing DP.

flowchart TD
  accTitle: Dynamic-programming pattern and dimension chooser
  accDescr: Start from the decisions and repeated subproblems. Use one-dimensional DP for one changing prefix or amount, two-dimensional DP for two prefixes, grid coordinates, or intervals, three-dimensional DP when a third independent constraint such as a second robot or transaction state changes the future, and sparse tuple memoization for higher-dimensional state. Then identify a specialized family such as knapsack, tree, interval, subset, or digit DP.
  A{"Can choices lead to the<br/>same remaining problem?"}
  A -->|no| B["Backtracking, greedy,<br/>or direct traversal"]
  A -->|yes| C["Write the smallest complete<br/>state tuple"]
  C --> D{"How many independent facts<br/>change the future?"}
  D -->|"one: i, amount, node"| E["1D / linear-state DP"]
  D -->|"two: i,j or left,right"| F["2D DP"]
  D -->|"three: row,c1,c2<br/>or day,k,holding"| G["3D DP"]
  D -->|"four or more"| H["Sparse tuple / bitmask DP<br/>and state reduction"]
  E --> I{"Special structure?"}
  F --> I
  G --> I
  H --> I
  I -->|"capacity + item choice"| J["Knapsack family"]
  I -->|"subtree / interval / subset"| K["Structured DP"]
  I -->|"numeric bound digit by digit"| L["Digit DP"]
  I -->|"ordinary sequence or grid"| M["Use dimensional guide"]

Dimension is about state, not input

A matrix problem is not automatically 2D DP, and an array problem is not automatically 1D DP.

State contract	Dimension	Typical pattern
dp[i] = answer for the first i values	1D	take/skip, stairs, LIS
dp[amount] = best way to make amount	1D	coin change
dp[i][j] = answer for two prefixes	2D	LCS, edit distance
dp[left][right] = answer inside an interval	2D	interval DP
dp[row][c1][c2] = two agents after row	3D	Cherry Pickup II
dp[day][used][holding] = trading state	3D	bounded stock trades
(pos, tight, started, mask)	4D tuple	digit DP
(node, parent_taken)	logical 2D	tree DP

Count only independent facts. In a two-robot grid, both robots are on the same row after the same number of moves, so (row, c1, c2) is sufficient; storing both row coordinates would be redundant.

The solve-before-code workflow

flowchart LR
  accTitle: From brute force to a correct dynamic program
  accDescr: Draw the decision tree, name the recursive contract, merge nodes with identical future information into states, write transitions and base cases, choose a dependency order, compute state and transition complexity, and only then compress memory or reconstruct a solution.
  A["Draw decisions"] --> B["Name recursive contract"]
  B --> C["Merge equivalent futures"]
  C --> D["Write recurrence"]
  D --> E["Base + impossible states"]
  E --> F["Choose evaluation order"]
  F --> G["Count states × work/state"]
  G --> H["Optimize / reconstruct"]

For each problem, write this sentence:

solve(state) returns ___ for exactly , assuming .

Then complete the five-part definition:

1. State — the exact meaning of every coordinate.
2. Transition — each legal decision and the next state it creates.
3. Base — solved terminal states and impossible states.
4. Order — why dependencies are ready before a state reads them.
5. Answer — the precise state or aggregate the problem requests.

The state-design workshop applies this method step by step.

Pattern router

Problem signal	First model	Detailed guide
choose or skip along one sequence	dp[i] or two rolling values	1D DP
transform/compare two strings	dp[i][j] over prefixes	2D DP
move through a grid	dp[row][column]	2D DP
two synchronized agents	dp[step][position1][position2]	3D DP
bounded actions plus mode	dp[time][budget][mode]	3D DP
use each item once or repeatedly	capacity DP + deliberate loop direction	Knapsack families
choose the final split inside a range	dp[left][right]	Structured DP
result from child subtrees	return a small state vector per node	Structured DP
n is around 15–22 and chosen set matters	dp[mask] or dp[mask][last]	Higher-dimensional DP
count values up to a huge numeric bound	digit position + bound flags + property	Higher-dimensional DP
need the actual choices, not only the score	parent/choice pointers	Optimization and reconstruction

Memoization or tabulation?

Top-down memoization	Bottom-up tabulation
mirrors the decision recurrence	makes dependency order explicit
visits only reachable states	usually fills the declared state space
handles irregular tuple states naturally	has predictable memory access
risks call-stack depth	supports rolling-array compression easily

They are two evaluation strategies for the same state graph. Start with the one that makes correctness easiest to explain. Convert only for recursion depth, constant factors, memory layout, or reconstruction.

Detailed guides

• State design and proof
• 1D DP: sequences, take/skip, and amounts
• 2D DP: grids, two strings, and intervals
• 3D DP: two agents, resources, and state machines
• Higher-dimensional, sparse, bitmask, and digit DP
• Knapsack families and loop direction
• Interval, tree, DAG, subset, and game DP
• Space optimization, reconstruction, and debugging

Tested anchor: 0/1 knapsack

For each item (weight, value), update capacity in descending order.

State: best[c] is the best value with capacity at most c using items processed so far.

Invariant: before best[c] is written, best[c - weight] still belongs to the previous item layer. Ascending order would reuse the current item and solve unbounded knapsack instead.

PythonC++17C++11

def knapsack_01(capacity: int, items: Iterable[tuple[int, int]]) -> int:
    """Return the maximum value when every item can be used at most once."""
    if capacity < 0:
        raise ValueError("capacity must be nonnegative")

    best = [0] * (capacity + 1)
    for weight, value in items:
        if weight <= 0:
            raise ValueError("item weights must be positive")
        # Descend so best[current - weight] still belongs to the prior item layer.
        for current in range(capacity, weight - 1, -1):
            best[current] = max(best[current], best[current - weight] + value)
    return best[capacity]

inline long long knapsack_01(
    int capacity, const std::vector<std::pair<int, int>>& items) {
  if (capacity < 0) {
    throw std::invalid_argument("capacity must be nonnegative");
  }
  std::vector<long long> best(capacity + 1, 0);
  for (const auto& item : items) {
    const int weight = item.first;
    const int value = item.second;
    if (weight <= 0) {
      throw std::invalid_argument("item weights must be positive");
    }
    // Descend so the source state still belongs to the prior item layer.
    for (int current = capacity; current >= weight; --current) {
      best[current] =
          std::max(best[current], best[current - weight] + value);
    }
  }
  return best[capacity];
}

inline long long knapsack_01(
    int capacity, const std::vector<std::pair<int, int>>& items) {
  if (capacity < 0) {
    throw std::invalid_argument("capacity must be nonnegative");
  }
  std::vector<long long> best(capacity + 1, 0);
  for (const auto& item : items) {
    const int weight = item.first;
    const int value = item.second;
    if (weight <= 0) {
      throw std::invalid_argument("item weights must be positive");
    }
    // Descend so the source state still belongs to the prior item layer.
    for (int current = capacity; current >= weight; --current) {
      best[current] =
          std::max(best[current], best[current - weight] + value);
    }
  }
  return best[capacity];
}

Source-grounded practice

The examples are organized against the official LeetCode Dynamic Programming study plan and HackerRank’s Dynamic Programming interview kit. The state-first method follows MIT’s view of DP as subproblems plus guesses in a dependency DAG: Dynamic Programming Subproblems.

Practice rule

Do not memorize a table shape from a solution. For every practice problem, write the state contract and recurrence before opening an editor.