Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 63 ยท Practice and Review

CSES DP Problems Walkthrough

A guided tour of the CSES dynamic programming section: coin problems, knapsack, edit distance, counting towers, interval games, bitmask and broken-profile DP, all tested in Python.

The Dynamic Programming section of the CSES Problem Set is a compact course in state design. Its 19 problems cover the whole ladder: one-dimensional tables (coins, dice), two-dimensional tables (edit distance, knapsack, grids), interval DP, DP over subsets, and DP over the profile of a grid. If you can solve them all, most "easy to medium" DP problems on any contest site will look familiar.

This lesson explains the central idea of the problems that teach something new, and gives original, tested Python for each. The statements are my own paraphrases; read the originals on the CSES site, and treat each solution here as a hint ladder to climb only after you have tried the problem. For the underlying theory see DP Problem Patterns and Bitmask and Digit DP.

flowchart TD
    Q["A counting or optimizing problem"] --> S["What is the smallest information that decides the future?"]
    S --> A["A number: coins, dice, books"]
    S --> B["Two indices: edit distance, intervals"]
    S --> C["A set of used items: bitmask"]
    S --> D["The edge of a partial grid: profile"]
    A --> T["Write the transition, check base cases"]
    B --> T
    C --> T
    D --> T

The first job in every DP problem is to name the state.

Problems on one amount: coins, books and sums

Coin Combinations I and II, Minimizing Coins. You have coin values and a target sum. Three questions, one table f[s]:

  • Minimizing Coins: f[s] = 1 + min(f[s - c]), fewest coins.
  • Coin Combinations I: count ordered sequences of coins with sum s (1 then 2 differs from 2 then 1). f[s] = sum of f[s - c] over coins, with the amount as the outer loop.
  • Coin Combinations II: count unordered sets. Put the coin as the outer loop, so each coin type is introduced once and order cannot matter.

Swapping the loop order is the single most common DP mistake in this family, and the lesson here is that the loop order is part of the model.

Book Shop is the 0/1 knapsack: each book at most once. Iterate the budget downwards inside each book so a book cannot be reused in the same pass. Money Sums asks for every sum obtainable by a subset of coins. In Python, keep the reachable set as one huge integer (a bitset) and update it with reach |= reach << c, which handles thousands of coins quickly.

Edit Distance is the classic two-string table: d[i][j] is the cheapest way to turn the first i letters of a into the first j letters of b, taking the minimum of delete, insert and substitute (free if the letters match). Keeping only the previous row reduces memory to O(len(b)).

Python Coins, books, money sums and edit distance

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.

Each function is verified against a recursion or an enumeration of all choices on small inputs. The printed example shows ordered versus unordered counts differing for the same coins: 8 against 3 for the target 9.

Counting towers, a removal game and weighted intervals

Counting Towers. A tower of width 2 is built from rectangular blocks of width 1 or 2 and any height; count the distinct towers of height h for many queries up to h = 10^6. Look only at the top row. It is either covered by one wide block ("joined") or by two blocks ("split"). Going up one row you can extend blocks or end them and start new ones. This gives two linked sequences:

  • joined[h] = 2 * joined[h-1] + split[h-1]
  • split[h] = joined[h-1] + 4 * split[h-1]

and the answer is their sum, which starts 2, 8, 34, 148, 650, ... The code confirms the formula by enumerating every tiling for small heights. Precompute once up to the largest query so each query is O(1).

Removal Game. Two players take numbers alternately from either end of a row, and each wants the biggest personal total. Define diff[l][r] as the best (my total minus opponent total) for the segment l..r when I move first. If I take the left end, the opponent then plays optimally on l+1..r, so my advantage is a[l] - diff[l+1][r]; the right end gives a[r] - diff[l][r-1]. Take the larger. Finally my total is (sum + diff) / 2. This is interval DP, filled by increasing segment length, and it is the same minimax logic as in Game Theory.

Projects. Projects have a first day, a last day and a reward; choose non-overlapping ones to maximize the reward. Sort by end day. best[i] is the best reward using the first i projects; for project i, either skip it (best[i-1]) or take it and add best[j] where j counts the projects that end strictly before it starts. Find j with bisect. This is weighted interval scheduling, the weighted cousin of the greedy Movie Festival.

Python Counting towers, the removal game and projects

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.

Subsets and profiles: elevator rides and domino tilings

Elevator Rides. n people (up to 20) with weights and an elevator of capacity x; minimize the number of rides. With n up to 20 the intended state is the set of people already transported. For each mask, store the pair (rides, weight in the last ride), and compare pairs lexicographically: fewer rides first, then a lighter current ride. To extend a mask by person i, either they fit into the current ride or you start a new one. That is 2^n * n steps. The test compares it against all permutations for tiny cases.

Counting Tilings. Count the ways to tile an n by m grid (here up to 10 by 1000 in the original) with dominoes. The trick is the broken profile: scan cell by cell and keep a bitmask of the next m cells that are already covered by a vertical domino poking down from above. At a covered cell, move on. At a free cell, either put a vertical domino (marking the cell below) or a horizontal one (covering the cell to the right, if it is free). The number of states is 2^m, and there are n * m cells. The code validates against backtracking on every grid up to 5 by 5 and prints two well-known values: 781 tilings for 4 by 7, and 12,988,816 for the 8 by 8 board.

Array Description. Count the arrays of values in 1..m whose neighbors differ by at most 1, with some positions fixed (0 means free). The state is the current value: ways[v] is the number of ways for the prefix so far ending in v, and the next position's ways'[v] is the sum of ways[v-1], ways[v], ways[v+1] if v is allowed there, otherwise 0. Pad the table by one cell on each side to avoid boundary checks.

Python Elevator rides, domino tilings and array descriptions

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.

The remaining DP problems

  • Dice Combinations and Removing Digits: one-dimensional tables, the simplest warm-ups (the second takes a digit away each step; the table at s is 1 + min f[s - digit]).
  • Grid Paths, Rectangle Cutting, Longest Common Subsequence, Increasing Subsequence: two-dimensional tables or the patience-sorting trick; see DP Problem Patterns.
  • Two Sets II: count ways to split 1..n into two sets of equal sum; a subset-sum counting DP over the target sum / 2.
  • Mountain Range: memoized longest chain with a monotonic stack for the neighbors.
  • Counting Numbers (no equal neighbors): digit DP, see Bitmask and Digit DP.
  • Minimal Grid Path: a layered BFS that keeps all cells with the same smallest string so far.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. To count the number of unordered sets of coins that sum to s, which loop order is right?

    With the coin as the outer loop each coin type is added once and combinations are built in a fixed coin order, so 1+2 and 2+1 are counted once.
  2. 2. Why does the Book Shop knapsack iterate the budget downwards?

    Going upwards would let best[money - price] already include the same book, turning the problem into an unbounded knapsack.
  3. 3. In the removal game, what does diff[l][r] represent?

    Taking an end gives that value minus the opponent's best advantage on the rest. Total = (sum + diff) / 2 for the first player.
  4. 4. What does the bitmask hold in the broken-profile domino DP?

    Scanning cell by cell, the profile records the frontier: the next m cells and whether each is already covered.

Summary

  • Name the smallest state that decides the future: an amount, two indices, a set of used items, or a grid frontier.
  • Loop order encodes the model: amount outermost counts orderings; coin outermost counts sets. Knapsack direction decides reuse.
  • Interval DP (Removal Game) fills by length; weighted interval scheduling (Projects) sorts by end and binary searches the predecessor.
  • Bitmask DP with a pair (rides, last load) solves packing problems for n <= 20; profile DP handles tilings with 2^width states.
  • Verify each DP against a brute force on tiny inputs before trusting a large run.

Next: CSES Graph Problems Walkthrough