Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 63 ยท Dynamic Programming for Contests

DP Problem Patterns

A repeatable recipe for contest DP: define the state, write the transition, set base cases and iterate in the right order, with coin, knapsack and LCS examples.

Dynamic programming (DP) is the topic contestants fear most, and the reason is simple: there is no single formula. But strong contestants do not invent a fresh trick each time. They run the same short recipe on every problem, and a surprisingly small set of patterns repeats across hundreds of tasks. This lesson gives you the recipe and the four patterns you will use most: counting and optimizing over a line, knapsacks, two-sequence tables and grids.

If DP is new, start with DP Introduction, 1D DP and Knapsack. Here we concentrate on the contest habits: how to choose a state quickly, what order to loop in, and how to test a DP against a brute force.

The recipe

Ask these five questions, in order, and write the answers as comments before any code.

  1. State. What is the smallest description of a subproblem? dp[i], dp[i][j], dp[i][mask]. Include only what affects the future.
  2. Meaning. In one sentence: "dp[i] is the minimum number of coins to make exactly i".
  3. Transition. How does a state follow from smaller states? Usually a min, max or sum over a few options.
  4. Base case. What do you know without recursion? Usually the empty prefix: dp[0] = 0 or 1.
  5. Order. In which order must states be computed so that every dependency is ready? Then: where is the answer, and what are the sizes?
flowchart LR
    A["State and meaning"] --> B["Transition"]
    B --> C["Base cases"]
    C --> D["Evaluation order"]
    D --> E["Answer cell and complexity"]

Write these five answers down before coding.

A check on cost: states times transitions per state is the time. With a state count of 10^6 and 3 transitions each, plain Python is fine. At 10^8 operations it is not (see Estimating Time and Memory).

Pattern 1: one dimension, coin-style

Three problems share almost the same code, and they differ in a way that is easy to get wrong.

  • Fewest coins to make T: dp[x] = min(dp[x - c] + 1).
  • Number of combinations (order does not matter, 1+2 and 2+1 are the same): loop over coins on the outside, amounts inside.
  • Number of sequences (order matters): loop over amounts on the outside, coins inside.

The loop order is the meaning. In the combinations version, once you finish a coin you never use it earlier in the sequence again, so each multiset is counted once. In the sequences version, any coin may come at any position.

Python Coin DP: fewest, combinations, sequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pattern 2: knapsack and the direction of the loop

In a 0/1 knapsack each item can be used at most once. In an unbounded knapsack each item can be used any number of times. With a one-dimensional array dp[w] (best value with capacity w), the two differ only in the direction of the capacity loop:

  • 0/1: loop w from high to low. When you update dp[w] from dp[w - weight], that older cell has not been touched by the current item yet, so the item is used once.
  • Unbounded: loop w from low to high. The cell dp[w - weight] may already include this item, which is what you want.

Getting the direction wrong silently turns one problem into the other. Many "wrong answer on test 2" bugs are exactly this.

Bounded knapsack (item i available k times) can be handled by splitting the count into binary pieces (1, 2, 4, ..., remainder) and solving a 0/1 knapsack on the pieces. For subset-sum feasibility the array can store booleans, or even a Python integer used as a bitset: bits |= bits << weight.

Python Knapsack loop direction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pattern 3: two sequences, a 2D table

When the input is two strings or sequences, the state is usually dp[i][j]: "the answer for the first i items of A and the first j items of B". Longest common subsequence (LCS), edit distance and many matching problems fit this shape. The transition looks at the last items:

  • If A[i-1] == B[j-1], extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1.
  • Otherwise take the better of dropping one item: max(dp[i-1][j], dp[i][j-1]).

Row 0 and column 0 are the base cases (an empty prefix). Rows depend only on the previous row, so you can keep two rows when memory is tight, but keep the full table if you need to reconstruct the answer by walking backwards.

The same layout also solves grid path problems: dp[r][c] is the best cost to reach cell (r, c) coming from above or from the left.

Python LCS with reconstruction and a grid path DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Evaluation order: forward, backward and memoization

There are two equivalent ways to evaluate a DP:

  • Bottom-up (tabulation): fill the table in an order where dependencies are ready. It is fast and has no recursion limit.
  • Top-down (memoization): write the recursion and cache results with functools.lru_cache. It is easy to write when the order is awkward, but Python's recursion limit (about 1000) can bite, and function calls are slow.

If you can write the table order in one sentence ("rows top to bottom, columns left to right"), go bottom-up. If the transitions jump around, memoize first to get a correct solution, then convert if it is too slow.

Another useful distinction is pull versus push. Pull computes dp[i] by looking back at earlier states. Push, after finishing dp[i], sends contributions forward to later states. Both give the same table; choose the one whose transitions are easier to enumerate. Push is natural for "from here I can jump to these places".

DP on a directed acyclic graph

Every DP you have seen so far has hidden structure: a state depends on states "before" it. Make that structure explicit and you get a directed acyclic graph (DAG): vertices are states, an edge u -> v means "v can use the answer of u". A DAG has a topological order, a list in which every edge points forward, and processing the vertices in that order guarantees that all inputs of a state are ready when you reach it. Coin change, knapsack, edit distance and shortest paths in a DAG are all instances.

The recipe for any DAG problem:

  1. Compute a topological order (Kahn's algorithm: repeatedly remove vertices with in-degree zero). If fewer than all vertices are removed, the graph has a cycle.
  2. Define dp[v] as the best answer for paths ending at v (or starting at v, processed in reverse order).
  3. Walk the order and relax each outgoing edge: dp[v] = combine(dp[v], dp[u] + cost).

What combine does decides the problem: max gives the longest path, min the cheapest path (valid even with negative edge weights, unlike Dijkstra), + counts paths. The cost is O(n + m).

Cycles and redundancy. A cycle breaks the topological order. In a "longest path" problem a cycle usually makes the answer unbounded, and you must report that (for instance print -1) before running the DP. In counting problems, check that the graph really is acyclic, or count only on the reachable part. Redundant edges (an edge a -> c when a -> b -> c exists) do not change reachability but they do change counts, so decide whether the problem counts paths or just asks about reachability.

Extra dimensions. Sometimes the state needs more than the vertex. "The largest number of vertices of one color on any path" can be solved with one DP pass per color (cnt[v] = max over predecessors + 1 if v has that color), at a cost of O(k (n + m)) for k colors, or with a map of counts per vertex when colors are many but paths are short. The general idea: when the answer for a vertex is a vector, make the vector part of the state.

Python DP on a DAG: longest path, path counting, color counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • State is too big or too small. If answers depend on something your state forgot (such as the last chosen value), the DP is wrong; if the state keeps something useless, it is too slow.
  • Missing base case or wrong sentinel. Use infinity for "impossible" in min problems, 0 for "no ways" in counting, and negative infinity in max problems. Do not use -1 and then take a min.
  • Modulo forgotten. When counting, reduce modulo the prime as soon as you add: see Modular Arithmetic.
  • Not testing. Every DP in this lesson was checked against a brute force on tiny inputs; do the same, as described in Stress Testing with a Brute Force.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. To count the number of ordered sequences of coins (1+2 and 2+1 count separately) that sum to T, which loop should be on the outside?

    With amounts outside, every coin may be the last one at every amount, so orders count separately. Coins outside counts each multiset once.
  2. 2. In a one-dimensional 0/1 knapsack, why must the capacity loop go from high to low?

    Going high to low means the lower cell has not yet been updated by this item. Going low to high would let the same item be reused.
  3. 3. Which is a sound sentinel for impossible states in a minimization DP?

    Infinity never wins a min and stays larger than any real answer. A value such as -1 or 0 would be picked as the minimum by mistake.
  4. 4. When is top-down memoization the better first attempt?

    Memoization removes the need to find an order. Keep recursion depth in mind, and convert to a table if it is too deep or too slow.

Summary

  • Run the recipe: state, meaning, transition, base case, order; then compute states times transitions.
  • Coin problems: the loop order decides between combinations and sequences.
  • 0/1 knapsack loops capacity downward; unbounded loops upward; subset sums can use integer bitsets.
  • Two-sequence problems use a table dp[i][j] over prefixes, and you can walk the table backwards to rebuild an answer.
  • Choose bottom-up for speed and memoization for awkward orders; always test with a brute force.

Next: Bitmask and Digit DP