DP Thinking Framework: How to Design States

Summary. A meta-guide that teaches you how to recognize DP problems, define states, find transitions, and optimize -- the systematic process behind every DP solution.

Prerequisites. DP Intro * Complete Search

Difficulty. [Beginner->Intermediate] CF 1200-1800 Target range. CF 1100->2100

Quick Revisit

• USE WHEN: you need a systematic approach to define DP states for a new problem
• INVARIANT: the state must capture all information needed to make future decisions
• TIME: O(states * transitions) | SPACE: O(states)
• CLASSIC BUG: state missing a dimension -- two different subproblems collide in the same cell
• PRACTICE: DP Practice Ladder

Contents

• Intuition
• The 4-Step DP Design Process
• The 6 State Archetypes
• State Reduction Techniques
• Worked Examples from Scratch
• Decision Flowchart
• Common Mistakes in DP Design
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Consider a simple problem: find the minimum number of coins (denominations $1,3,4$) to make change for $n=6$.

A brute-force recursion tries every denomination at every step:

                        solve(6)
                      /    |    \
                 solve(5) solve(3) solve(2)
                /  |  \    / | \    / | \
           s(4) s(2) s(1) ...  ...  ...
          / | \
       s(3) s(1) s(0)
       ...

Count how many times solve(2) appears:

solve(6) -> solve(5) -> solve(2)            [1st time]
solve(6) -> solve(3) -> solve(2)            [2nd time]
solve(6) -> solve(5) -> solve(4) -> solve(1) -> ... (leads to solve(2) again)
solve(6) -> solve(5) -> solve(2)            (same path, different branch)
solve(6) -> solve(2)                        [3rd time]

The subproblem solve(2) is solved at least 5 times in this tiny tree. For $n=100$, the recursion tree has $O(3^n)$ nodes -- most of them redundant. The subproblem space is only $O(n)$, but brute force doesn't know that.

This is the hallmark of a problem begging for DP: exponential brute force, polynomial subproblem space.

DP = recursion + memoization. If the same subproblem appears multiple times, store its answer and reuse it.

That single sentence is the entire idea. Everything else -- bottom-up tables, state transitions, optimizations -- is implementation detail around this core principle.

The reason DP works is two properties:

1. Optimal substructure. The optimal solution to the whole problem can be built from optimal solutions to subproblems.
2. Overlapping subproblems. The same subproblems appear many times in the recursion.

If you have (1) but not (2), use divide-and-conquer. If you have (2) but not (1), DP won't give optimal answers. If you have both, DP transforms exponential into polynomial.

Visual Walkthrough

Before memoization -- the recursion tree for solve(6) with coins $\{1,3,4\}$:

                          solve(6)
                       /     |     \
                    s(5)    s(3)   s(2)
                  / | \    / | \   / | \
               s(4) s(2) s(1) s(2) s(0) s(1) s(-2)
              /|\   /|\   |     X    *    |     X
           s(3)... ... s(0) ...      s(0)
                        *              *

   X = pruned (negative)    * = base case (0 coins needed)

Notice: s(2) appears 3+ times. s(3) appears 2+ times. s(1) appears 3+ times. Every repeated node triggers its entire subtree again.

After memoization -- each subproblem solved exactly once:

   s(0) = 0       (base case)
   s(1) = 1       (only 1-coin works: 0+1)
   s(2) = 2       (1+1: memo[2] = 2, done, never recomputed)
   s(3) = 1       (one 3-coin: memo[3] = 1)
   s(4) = 1       (one 4-coin: memo[4] = 1)
   s(5) = 2       (min of memo[4]+1, memo[2]+1, memo[1]+1 = 2)
   s(6) = 2       (min of memo[5]+1, memo[3]+1, memo[2]+1 = 2)

From $O(3^n)$ nodes down to $O(n)$ computations. Each node is visited once, its answer stored in memo[], and every future call returns instantly.

The Invariant

dp[state] stores the optimal answer for the subproblem defined by state. Once computed, it never changes.

This is the contract every DP solution must uphold. If dp[i] can be "updated" later by a better answer, your state definition is wrong or your traversal order is wrong.

In top-down (memoization): the recursion naturally ensures each state is computed from already-computed substates.

In bottom-up (tabulation): you must iterate in an order that guarantees all dependencies of dp[i] are filled before you compute dp[i]. Think of it as filling in a spreadsheet: each cell's formula references only cells that are already computed. The real creative step is deciding what the rows and columns represent -- once you have that, you just fill left-to-right, top-to-bottom (or whatever order respects the dependencies), and the answer appears in the final cell.

What the Code Won't Teach You

These insights come from designing DPs, not from reading implementations.

The state design process: start with "what changes between subproblems?" Look at two different recursive calls. What parameters differ? Those differing parameters are your state. Everything else is constant and shouldn't be part of the DP table. If nothing seems to change, you haven't decomposed the problem into subproblems yet.

The "exchange argument" test for greedy vs DP. Before reaching for DP, try to prove a greedy choice is always safe. The exchange argument works like this: take any optimal solution that doesn't follow the greedy rule, swap two adjacent elements to follow it, and show the result is no worse. If you can prove this, greedy works and DP is overkill. If you can construct a counterexample where greedy fails, then reach for DP.

Transition design: "pull" vs "push." There are two equivalent ways to write transitions:

• Pull (backward): "To compute dp[i], which earlier states do I read from?" -> $\text{dp}[i]=f(\text{dp}[j_1],\text{dp}[j_2],\dots )$
• Push (forward): "From state dp[i], which later states do I update?" -> for each decision, update $\text{dp}[j]$ using $\text{dp}[i]$

Pull is more natural for bottom-up (you fill each cell once). Push is more natural when the set of outgoing transitions is easier to enumerate than the set of incoming ones.

  Pull transitions (backward):          Push transitions (forward):

  "Who feeds into me?"                  "Where do I send my value?"

   dp[0]   dp[1]   dp[2]   dp[3]        dp[0]   dp[1]   dp[2]   dp[3]
                      ^                    |  \
                     / \                   v    v
                dp[0]   dp[1]            dp[1]  dp[2]
                                           |  \
       To compute dp[2], look              v    v
       back at dp[0] and dp[1].          dp[2]  dp[3]

                                         From dp[0], push to
                                         dp[1] and dp[2]. Then
  Each cell READS from earlier.          from dp[1], push to
  dp[i] = min(dp[i-1]+1, dp[i-2]+3)     dp[2] and dp[3].

How to add dimensions incrementally. Don't try to guess the perfect state on your first attempt. Instead:

1. Start with the simplest state (usually just an index).
2. Code it, submit, get WA.
3. Ask: "What information am I losing between subproblems?"
4. Add that as a new dimension. Repeat.

This is faster than trying to design the complete state up-front, especially under contest pressure.

  THE STATE DESIGN PROCESS

  +--------------------+
  | Problem statement  |
  +--------------------+
           |
           v
  +--------------------+
  | What varies between|   "Which item am I on? How much capacity
  | subproblems?       |    remains? What was the last choice?"
  +--------------------+
           |
           v
  +--------------------+
  | Minimal state that |   Remove anything derivable from other
  | captures all info  |   dimensions. Keep only what's needed.
  +--------------------+
           |
           v
  +--------------------+
  | Write recurrence   |   dp[state] = opt(dp[next_states] + cost)
  +--------------------+
           |
           v
  +--------------------+
  | Verify: do 2 calls |   If same state -> different answers,
  | with same state    |   add a dimension. If always same,
  | give same answer?  |   state is correct.
  +--------------------+

When to Reach for This

Reach for DP when you see these signals:

Signal	Example phrasing
Optimal substructure	"minimum cost", "maximum profit", "longest subsequence"
Overlapping subproblems	Recursion with same arguments called repeatedly
Counting paths/ways	"how many ways to ...", "count the number of ..."
Decision at each step	"take or skip", "go left or right", "include or exclude"
Small constraints with exponential brute force	$n\le 1000$ but brute force is $O(2^n)$

If the problem says "minimum/maximum" and greedy doesn't work (no exchange argument), DP is almost certainly the approach.

---

The 4-Step DP Design Process

Every DP solution, from the simplest staircase problem to the hardest bitmask DP, follows these four steps. Master this process and you can derive any DP from scratch.

Step 1: Define the State

"What information do I need to describe a subproblem uniquely?"

The state is a tuple of parameters that fully describes a subproblem. Two calls with the same state must return the same answer.

How to find the state:

1. Start with the brute-force recursion.
2. Look at the parameters you pass to recursive calls.
3. Remove parameters that don't affect the answer.
4. What remains is your state.

Example -- Knapsack: You have $n$ items, each with weight $w_i$ and value $v_i$, and a capacity $W$. The brute force considers item $i$ and either takes or skips it. What do you need to know?

• Which item you're considering: index $i$
• How much capacity remains: $c$
• State: $(i,c)$, so dp[i][c]

Common mistake: Including information you don't need. If the order of previously chosen items doesn't matter, don't encode it.

Step 2: Define the Transition

"How do states relate to each other? What choices lead from one state to another?"

The transition is the recurrence relation. It expresses dp[state] in terms of smaller/simpler states.

How to find the transition:

1. At state $S$, what decisions can you make?
2. Each decision leads to a new state $S^{\prime }$.
3. Combine the results: $\text{dp}[S]=\text{opt}(\text{dp}[S^{\prime }]+\text{cost of decision})$

Example -- Knapsack:

$$\text{dp}[i][c]=max(\text{dp}[i-1][c],\text{dp}[i-1][c-w_i]+v_i)$$

The first term: skip item $i$. The second term: take item $i$ (only if $c\ge w_i$).

Common mistake: Not considering all choices. If you have 3 options at each step, your transition must account for all 3.

Step 3: Define the Base Cases

"What are the smallest subproblems whose answers are immediately known?"

Base cases are the termination conditions of your recursion. Without them, the recurrence has no foundation.

How to find base cases:

1. What happens when the state parameters hit their boundary values?
2. An empty set, zero capacity, index past the last element, etc.

Example -- Knapsack:

• $\text{dp}[0][c]=0$ for all $c$ (no items to consider, zero value)
• $\text{dp}[i][0]=0$ for all $i$ (zero capacity, can't take anything)

Common mistake: Forgetting edge cases. What if $c<0$? Return $-\mathrm{\infty }$ (or handle via bounds checking).

Step 4: Define the Answer

"Which state(s) contain the final answer?"

Sometimes it's a single cell: $\text{dp}[n][W]$. Sometimes it's the maximum over an entire row: $\underset{i}{max}\text{dp}[n][i]$. Sometimes it's more subtle.

Example -- Knapsack: $\text{dp}[n][W]$ directly gives the maximum value using all $n$ items with capacity $W$.

Example -- LIS: $\underset{i=1}{\overset{n}{max}}\text{dp}[i]$, since the longest increasing subsequence can end at any position.

Summary of the 4 steps:

+--------------------------------------------------+
|  1. STATE:      What describes a subproblem?      |
|  2. TRANSITION: How do states connect?            |
|  3. BASE CASE:  Where does the recursion stop?    |
|  4. ANSWER:     Where is the final result?        |
+--------------------------------------------------+

---

The 6 State Archetypes

Most DP problems fall into one of six archetype families. Recognizing which archetype applies immediately narrows your state design.

Archetype 1: Index-Based

State: dp[i] = optimal answer considering the first $i$ elements (or ending at index $i$).

This is the most common DP shape. You process elements left to right, and the state tracks "how far along" you are.

Transition pattern:

$$\text{dp}[i]=f(\text{dp}[j]\text{ for }j<i)$$

Typical complexity: $O(n)$ to $O(n^2)$, depending on how many previous states each transition examines.

Problem	State meaning	Transition
Climbing Stairs	dp[i] = ways to reach step $i$	dp[i] = dp[i-1] + dp[i-2]
Coin Change	dp[i] = min coins for amount $i$	dp[i] = min(dp[i - c] + 1) for each coin $c$
LIS	dp[i] = length of LIS ending at $i$	dp[i] = max(dp[j] + 1) for $j<i$ where $a_j<a_i$

// Coin Change -- index-based DP
int solve(int n, vector<int>& coins) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int c : coins)
            if (c <= i && dp[i - c] != INT_MAX)
                dp[i] = min(dp[i], dp[i - c] + 1);
    return dp[n] == INT_MAX ? -1 : dp[n];
}

Archetype 2: Sum/Capacity-Based

State: dp[i][w] = optimal answer using the first $i$ items with capacity/budget $w$.

This adds a resource dimension to the index. The classic example is 0/1 Knapsack.

Transition pattern:

$$\text{dp}[i][w]=\text{opt}(\text{dp}[i-1][w],\text{dp}[i-1][w-w_i]+v_i)$$

Typical complexity: $O(n\cdot W)$ where $W$ is the capacity bound.

Problem	State meaning	Key idea
0/1 Knapsack	dp[i][w] = max value, $i$ items, capacity $w$	Take or skip each item
Subset Sum	dp[i][s] = can first $i$ elements make sum $s$?	Boolean version of knapsack
Bounded Knapsack	dp[i][w] with item counts	Binary lifting or monotone queue

// 0/1 Knapsack
int knapsack(int n, int W, vector<int>& wt, vector<int>& val) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];
            if (wt[i - 1] <= w)
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - wt[i - 1]] + val[i - 1]);
        }
    return dp[n][W];
}

Archetype 3: Bitmask-Based

State: dp[mask] = optimal answer for the subset of elements represented by the bitmask mask.

When $n\le 20$ and you need to track which elements have been used, encode the subset as a bitmask. Each bit indicates presence/absence.

Transition pattern:

$$\text{dp}[\text{mask}]={\text{opt}}_{i\in \text{mask}}(\text{dp}[\text{mask}\setminus \{i\}]+\text{cost}(i,\text{mask}))$$

Typical complexity: $O(2^n\cdot n)$ or $O(2^n\cdot n^2)$.

Problem	State meaning	Key idea
TSP	dp[mask][i] = min cost visiting mask, ending at $i$	Try all last cities
Assignment	dp[mask] = min cost assigning first $\text{popcount(mask)}$ jobs	Try all assignments for next person
Hamiltonian Path	dp[mask][i] = does path through mask ending at $i$ exist?	Boolean transitions

// TSP via bitmask DP
int tsp(int n, vector<vector<int>>& dist) {
    int full = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // start at city 0
    for (int mask = 1; mask <= full; mask++)
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX) continue;
            if (!(mask >> u & 1)) continue;
            for (int v = 0; v < n; v++) {
                if (mask >> v & 1) continue;
                int nmask = mask | (1 << v);
                dp[nmask][v] = min(dp[nmask][v],
                                   dp[mask][u] + dist[u][v]);
            }
        }
    int ans = INT_MAX;
    for (int u = 0; u < n; u++)
        ans = min(ans, dp[full][u] + dist[u][0]);
    return ans;
}

Archetype 4: Interval-Based

State: dp[l][r] = optimal answer for the subarray/subsequence from index $l$ to $r$.

When the problem involves merging or splitting contiguous segments, interval DP is the natural fit.

Transition pattern:

$$\text{dp}[l][r]={\text{opt}}_{k\in [l,r)}(\text{dp}[l][k]+\text{dp}[k+1][r]+\text{merge cost})$$

Typical complexity: $O(n^3)$ (can sometimes be reduced to $O(n^2)$ with Knuth's optimization).

Problem	State meaning	Key idea
Matrix Chain Mult.	dp[l][r] = min ops to multiply matrices $l..r$	Split at every $k$
Longest Palindromic Subseq.	dp[l][r] = LPS length in $s[l..r]$	Expand or shrink from ends
Burst Balloons	dp[l][r] = max coins from bursting $l..r$	Last balloon to burst

// Matrix Chain Multiplication
int mcm(vector<int>& dims) {
    int n = (int)dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            dp[l][r] = INT_MAX;
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r],
                    dp[l][k] + dp[k + 1][r]
                    + dims[l] * dims[k + 1] * dims[r + 1]);
        }
    return dp[0][n - 1];
}

Archetype 5: Digit-Based

State: dp[pos][tight][...] = count of valid numbers considering the first pos digits, with tight indicating whether we are still bounded by the upper limit.

Digit DP is used when you need to count numbers in $[1,N]$ satisfying some property (digit sum, specific digit patterns, divisibility).

Transition pattern:

$$\text{dp}[\text{pos}][\text{tight}][\dots ]=\sum _{d=0}^{\text{limit}}\text{dp}[\text{pos}+1][{\text{tight}}^{\prime }][{\dots }^{\prime }]$$

where $\text{limit}=\text{digit}[\text{pos}]$ if tight, else $9$.

Typical complexity: $O(\log N\cdot S)$ where $S$ is the extra state space.

Problem	Extra state	Key idea
Count numbers with digit sum $\le k$	Running digit sum	Accumulate sum across digits
Numbers without consecutive equal digits	Previous digit	Compare with last digit placed
Multiples of $m$ in range	Current remainder mod $m$	Track $\text{val}modm$

// Count integers in [1..N] with digit sum <= target
string num;
int target;
int memo[20][2][200];  // pos, tight, current_sum

int go(int pos, bool tight, int sum) {
    if (sum > target) return 0;
    if (pos == (int)num.size()) return 1;
    if (memo[pos][tight][sum] != -1) return memo[pos][tight][sum];
    int limit = tight ? (num[pos] - '0') : 9;
    int res = 0;
    for (int d = 0; d <= limit; d++)
        res += go(pos + 1, tight && (d == limit), sum + d);
    return memo[pos][tight][sum] = res;
}

int count(long long N) {
    num = to_string(N);
    memset(memo, -1, sizeof memo);
    return go(0, true, 0);
}

Archetype 6: Tree-Based

State: dp[v] = optimal answer for the subtree rooted at vertex $v$.

In tree DP, you process children before parents (post-order traversal). Each node aggregates results from its children.

Transition pattern:

$$\text{dp}[v]=f(\text{dp}[{\text{child}}_1],\text{dp}[{\text{child}}_2],\dots )$$

Typical complexity: $O(n)$ to $O(n^2)$, depending on how children are combined.

Problem	State meaning	Key idea
Tree diameter	dp[v] = longest path starting at $v$ going down	Combine two deepest children
Max independent set	dp[v][0/1] = max set, $v$ taken or not	If $v$ taken, children not taken
Tree knapsack	dp[v][w] = max value in subtree of $v$, weight $w$	Merge child knapsacks

// Maximum Independent Set on a tree
vector<int> adj[200001];
int dp[200001][2];  // dp[v][0] = v not taken, dp[v][1] = v taken
int val[200001];

void dfs(int v, int p) {
    dp[v][0] = 0;
    dp[v][1] = val[v];
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs(u, v);
        dp[v][0] += max(dp[u][0], dp[u][1]);
        dp[v][1] += dp[u][0];
    }
}

Archetype Quick-Reference

+-------------------+--------------+---------------------+-----------+
| Archetype         | State shape  | Typical trigger      | n limit   |
+-------------------+--------------+---------------------+-----------+
| Index-based       | dp[i]        | Linear sequence      | ~10^6     |
| Sum/capacity      | dp[i][w]     | Budget/weight limit   | ~10^3 x W|
| Bitmask           | dp[mask]     | "Subset", n <= 20    | ~20       |
| Interval          | dp[l][r]     | Merge/split segments  | ~500      |
| Digit             | dp[pos][..]  | Count in [1..N]      | ~10^18    |
| Tree              | dp[v]        | Rooted tree structure | ~10^5     |
+-------------------+--------------+---------------------+-----------+

---

State Reduction Techniques

Once you have a working DP, it might be too slow or use too much memory. These techniques help.

Rolling Array (Space Reduction)

When dp[i] depends only on dp[i-1], you don't need the full table. Keep only two rows (or even one).

0/1 Knapsack -- from $O(nW)$ space to $O(W)$:

vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++)
    for (int w = W; w >= wt[i]; w--)  // reverse order!
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

The reverse iteration is critical: it ensures each item is used at most once (processing forward would allow reuse, giving unbounded knapsack).

Top-Down vs Bottom-Up

Aspect	Top-down (memo)	Bottom-up (table)
Implementation	Recursive + cache	Iterative loops
States visited	Only reachable ones	All states in range
Stack overflow	Risk for deep recursion	No risk
Constant factor	Slightly slower (recursion overhead)	Slightly faster
Ease of coding	Often simpler	Sometimes tricky ordering

Rule of thumb: Start top-down for correctness. Convert to bottom-up if you need speed or the recursion depth exceeds the stack limit ($\sim {10}^6$ on most judges).

When DP Needs Further Optimization

If your DP is $O(n^2)$ or worse and the constraints demand better, look for these patterns:

Symptom	Optimization	New complexity
Transition is $min/max$ over a sliding window	Monotone deque	$O(n)$
Transition is $min(dp[j]+b_j\cdot a_i)$	Convex Hull Trick	$O(n\log n)$
Transition has Knuth's condition	Knuth's optimization	$O(n^2)$ from $O(n^3)$
Transition splits into independent halves	D&C optimization	$O(n\log n)$
States form a DAG with structure	Matrix exponentiation	$O(k^3\log n)$

Each of these is covered in its own file in this chapter.

---

Worked Examples from Scratch

Example 1: Coin Change (1D Index-Based)

Problem. Given coins of denominations $c_1,c_2,\dots ,c_k$, find the minimum number of coins to make amount $n$. (Unlimited supply.)

Step 1 -- State. What do I need? Just the remaining amount. $\text{dp}[i]$ = minimum coins to make amount $i$.

Step 2 -- Transition. For each coin $c$, I can use it if $c\le i$:

$$\text{dp}[i]=\underset{c\in \text{coins},c\le i}{min}(\text{dp}[i-c]+1)$$

Step 3 -- Base case. $\text{dp}[0]=0$ (zero amount needs zero coins). All other entries start at $\mathrm{\infty }$.

Step 4 -- Answer. $\text{dp}[n]$.

int coinChange(vector<int>& coins, int n) {
    const int INF = 1e9;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int c : coins)
            if (c <= i && dp[i - c] != INF)
                dp[i] = min(dp[i], dp[i - c] + 1);
    return dp[n] >= INF ? -1 : dp[n];
}

Complexity. $O(n\cdot k)$ time, $O(n)$ space.

Example 2: Unique Paths with Obstacles (2D Grid)

Problem. An $m\times n$ grid has obstacles (1) and free cells (0). Find the number of paths from $(0,0)$ to $(m-1,n-1)$ moving only right or down.

Step 1 -- State. Position on the grid. $\text{dp}[i][j]$ = number of paths from $(0,0)$ to $(i,j)$.

Step 2 -- Transition. You arrive from above or from the left:

$$\text{dp}[i][j]=\text{dp}[i-1][j]+\text{dp}[i][j-1]$$

If cell $(i,j)$ is an obstacle: $\text{dp}[i][j]=0$.

Step 3 -- Base case. $\text{dp}[0][0]=1$ if not an obstacle, else $0$. First row and column: propagate from the left/above, stopping at obstacles.

Step 4 -- Answer. $\text{dp}[m-1][n-1]$.

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] || grid[m - 1][n - 1]) return 0;
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    dp[0][0] = 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j]) { dp[i][j] = 0; continue; }
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    return dp[m - 1][n - 1];
}

Complexity. $O(m\cdot n)$ time and space.

Example 3: Where Greedy Fails -- Activity Selection with Weights

Problem. You have $n$ activities, each with start $s_i$, finish $f_i$, and weight $w_i$. Select non-overlapping activities to maximize total weight.

Why greedy fails. The classic "earliest finish time" greedy works for unweighted activity selection. But with weights, a single high-weight activity might beat many low-weight ones, and greedy can't decide without exploring both options.

Step 1 -- State. Sort by finish time. Let $p(i)$ = largest $j<i$ such that activity $j$ doesn't overlap with activity $i$. $\text{dp}[i]$ = max weight considering the first $i$ activities.

Step 2 -- Transition. For activity $i$, either skip it or take it:

$$\text{dp}[i]=max(\text{dp}[i-1],\text{dp}[p(i)]+w_i)$$

Step 3 -- Base case. $\text{dp}[0]=0$.

Step 4 -- Answer. $\text{dp}[n]$.

// Weighted Activity Selection
int solve(vector<array<int,3>>& acts) { // {finish, start, weight}
    sort(acts.begin(), acts.end());
    int n = acts.size();
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        // binary search for p(i): last non-overlapping activity
        int lo = 0, hi = i - 1, best = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (acts[mid][0] <= acts[i - 1][1])
                best = mid + 1, lo = mid + 1;
            else
                hi = mid - 1;
        }
        dp[i] = max(dp[i - 1], dp[best] + acts[i - 1][2]);
    }
    return dp[n];
}

Complexity. $O(n\log n)$ -- sort + binary search per activity.

Example 4: Non-Obvious State -- Edit Distance

Problem. Given two strings $a$ (length $m$) and $b$ (length $n$), find the minimum number of operations (insert, delete, replace) to transform $a$ into $b$.

Why the state isn't obvious. You might think: "I'm transforming a string, so the state should be the current string." But the current string can be exponentially many things. The insight: you only need to know how much of each string you've processed.

Step 1 -- State. $\text{dp}[i][j]$ = min operations to transform $a[0..i-1]$ into $b[0..j-1]$.

Step 2 -- Transition. Three choices:

$$\text{dp}[i][j]=min\{\begin{array}{ll}\text{dp}[i-1][j]+1& \text{(delete from }a\text{)}\\ \text{dp}[i][j-1]+1& \text{(insert into }a\text{)}\\ \text{dp}[i-1][j-1]+[a_{i-1}\ne b_{j-1}]& \text{(match/replace)}\end{array}$$

Step 3 -- Base case. $\text{dp}[0][j]=j$ and $\text{dp}[i][0]=i$.

Step 4 -- Answer. $\text{dp}[m][n]$.

int editDistance(string& a, string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = min({dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i - 1][j - 1] + (a[i-1] != b[j-1])});
    return dp[m][n];
}

Complexity. $O(m\cdot n)$ time and space ($O(n)$ space with rolling array).

Example 5: State Reduction -- Longest Increasing Subsequence

Problem. Find the length of the longest increasing subsequence of an array of $n$ elements.

Naive DP: $\text{dp}[i]$ = length of LIS ending at index $i$. Transition: $\text{dp}[i]=\underset{j<i,a_j<a_i}{max}(\text{dp}[j]+1)$. Complexity: $O(n^2)$. Too slow for $n={10}^5$.

State reduction insight. Instead of storing the LIS length ending at each index, maintain a separate array tails[] where tails[k] = the smallest ending element of any increasing subsequence of length $k+1$.

This array is always sorted, so we can binary search for the right position to update, reducing the $O(n)$ inner loop to $O(\log n)$.

int lis(vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return tails.size();
}

Complexity. $O(n\log n)$ time, $O(n)$ space.

The key idea: we didn't change the DP itself -- we changed what we store to enable faster queries. This pattern recurs throughout competitive programming: an $O(n^2)$ DP becoming $O(n\log n)$ by maintaining a smarter data structure over the DP values.

---

Decision Flowchart

Use this flowchart when you're staring at a problem and don't know where to start:

                    +----------------------------+
                    | Can you define subproblems  |
                    | with optimal substructure?  |
                    +----------------------------+
                          |            |
                         YES           NO
                          |            |
                          v            v
               +------------------+   Try greedy,
               | Do subproblems   |   graph algorithms,
               | overlap?         |   or math.
               +------------------+
                    |         |
                   YES        NO
                    |         |
                    v         v
              Use DP.    Use divide
                         & conquer.
                    |
                    v
         +---------------------+
         | What changes between |
         | subproblems?         |
         +---------------------+
          /    |     |    |    \
         v     v     v    v     v
      Index  Sum   Bits  Range  Tree
      (i)   (i,w) (mask) (l,r)  (v)
         \    |     |     |    /
          v   v     v     v   v
     +------------------------------+
     | Is it fast enough?            |
     +------------------------------+
          |                |
         YES               NO
          |                |
          v                v
       Submit.      Apply optimization:
                    - Rolling array
                    - Monotone deque
                    - CHT / Li Chao
                    - D&C optimization
                    - Knuth's opt.
                    - Matrix exponentiation

Digit DP branch (special case):

  "Count numbers in [L..R] with property P"
          |
          v
  Use digit DP: dp[pos][tight][extra state for P]

---

Common Mistakes in DP Design

Mistake 1: Wrong State Definition (Missing Information)

Symptom. Your DP gives wrong answers because two "different" subproblems map to the same state.

Example. In a problem where you process items and the answer depends on the last chosen item's color, but your state is just dp[i] (missing the color). Two subproblems with different last colors overwrite each other.

Fix. Add the missing dimension: dp[i][color].

Rule. If you can construct two scenarios with the same state but different optimal answers, your state is missing information.

Mistake 2: Wrong Transition (Not All Choices)

Symptom. Your DP gives suboptimal answers.

Example. In a problem where you can insert, delete, or replace characters, but your transition only considers insert and delete.

Fix. Enumerate ALL possible decisions at each state. Check the problem statement carefully for what operations are allowed.

Mistake 3: Wrong Base Cases

Symptom. Off-by-one errors, or the DP produces answers that are off by a constant.

Example. Setting dp[0] = 1 when it should be dp[0] = 0, or forgetting to handle the case when $i=0$ separately.

Fix. Trace your recurrence by hand for the smallest inputs. Does dp[0] match what you'd compute manually? Does dp[1]?

Mistake 4: Wrong Iteration Order

Symptom. Bottom-up DP gives wrong answers but top-down gives correct answers (or vice versa).

Example. In 0/1 knapsack with a 1D rolling array, iterating capacity forward instead of backward. This lets the same item be used multiple times.

Fix. Ensure that when you compute dp[state], all states it depends on are already finalized. Draw the dependency arrows:

dp[i][w] depends on dp[i-1][w] and dp[i-1][w - wt[i]]
         both from the PREVIOUS row
         => iterate w from high to low in 1D

Mistake 5: TLE From Too Many States

Symptom. Your solution is correct but too slow.

Example. A 3D DP with $n\times m\times k={10}^8$ states.

Fix checklist:

1. Can you reduce a dimension? (Maybe one parameter is derivable from the others.)
2. Can you use a rolling array to reduce memory?
3. Can you apply an optimization technique (see State Reduction)?
4. Is there a completely different state definition with fewer states?

Mistake 6: Wrong Loop Direction

Symptom. You write a correct recurrence, implement it bottom-up, but fill the table in the wrong order -- row-major when it should be column-major, or increasing $i$ when the transition needs $i+1$. The code runs, produces garbage, and you spend an hour debugging the transition when the real bug is the loop direction.

Fix. Always trace which states a cell depends on, then iterate so that dependencies are filled first.

Complexity Estimation for DP

Before you code any DP solution, do this 10-second sanity check:

Total complexity = (number of states) x (cost per transition)

Counting states. The number of states is the product of all dimension sizes. If your state is dp[i][j] with $0\le i<N$ and $0\le j<M$, you have $N\times M$ states. For dp[i][j][k], it's $N\times M\times K$. Simple multiplication -- but you'd be surprised how often people skip this and get burned.

Don't forget transition cost. This is the classic trap. A transition that loops over all previous elements isn't $O(1)$ -- it's $O(N)$ or $O(M)$, and that multiplies your state count.

Example -- the trap in action:

dp[i][j], where N = 5000, M = 5000

States:  5000 x 5000 = 2.5x10⁷

• If each transition is O(1) (e.g., dp[i][j] = dp[i-1][j] + dp[i][j-1]): -> Total: 2.5x10⁷ x 1 = 2.5x10⁷. Fine. Runs in ~100ms.

• If each transition loops over a dimension (e.g., dp[i][j] = min over all k of dp[i][k] + cost[k][j]): -> Total: 2.5x10⁷ x 5000 = 1.25x10¹¹. Hopelessly TLE. Need to optimize the transition (prefix sums, monotonic queue, Knuth's optimization, etc.).

Quick reference for DP state budgets (2-second TL, C++):

States	x O(1) transition	x O(N) transition (N=1000)
10⁶	✅ trivial	✅ 10⁹ -- borderline
10⁷	✅ fine	❌ 10¹⁰ -- TLE
10⁸	⚠️ tight	❌ hopeless
10⁹	❌ TLE	❌ hopeless

Rule of thumb: If your DP has more than ~10⁸ total work (states x transition cost), you need to either reduce dimensions or speed up transitions with a data structure.

Mental Traps

These are thinking patterns that feel productive but steer you wrong.

"I should recognize which standard DP type this problem is." Many problems require CUSTOM state definitions that don't fit any standard archetype. If you spend 10 minutes trying to force a problem into "knapsack" or "interval DP" and it doesn't fit, stop. The thinking framework is about derivation, not pattern matching. Go back to the 4-step process: define the brute-force recursion, extract the state, write the transition. The archetypes are shortcuts, not requirements.

"More state dimensions = better accuracy." Extra dimensions increase correctness only if they capture genuinely missing information. Otherwise they just explode your time and space complexity. The art is finding the MINIMAL state that captures all necessary information. A 4D DP that's correct but $O(n^4)$ is useless if a 2D DP with the right state is also correct and $O(n^2)$.

"If I can't see the recurrence immediately, DP doesn't apply." The recurrence often becomes clear only AFTER choosing the right state. If you're staring at the problem trying to see a formula, you're working backwards. Start from "what do I need to remember between subproblems?" -- the recurrence follows from the state, not the other way around. No one sees the recurrence first on hard problems.

  IS THIS A DP PROBLEM? -- Decision Flowchart

  +---------------------------+
  |  Read the problem.        |
  |  What are you optimizing  |
  |  or counting?             |
  +---------------------------+
               |
               v
  +---------------------------+
  |  Can you make decisions   |     NO
  |  that break the problem   +----------> Not DP.
  |  into smaller pieces?     |            Try greedy, math,
  +---------------------------+            or graph algorithms.
               |
              YES
               |
               v
  +---------------------------+
  |  Identify the decisions.  |
  |  "At each step, what      |
  |   choices do I have?"     |
  +---------------------------+
               |
               v
  +---------------------------+
  |  Identify the state.      |
  |  "What info do I need to  |
  |   describe where I am?"   |
  +---------------------------+
               |
               v
  +---------------------------+
  |  Write the recurrence.    |
  |  "dp[state] = best over   |
  |   all choices at state"   |
  +---------------------------+
               |
               v
  +---------------------------+
  |  Check: do subproblems    |     NO
  |  overlap?                 +----------> Use divide & conquer
  |  (same state reachable    |            instead (no memo needed).
  |   via multiple paths?)    |
  +---------------------------+
               |
              YES
               |
               v
  +---------------------------+
  |  DP applies. Implement    |
  |  top-down with memo or    |
  |  bottom-up with table.    |
  +---------------------------+

---

Debug Drills

Drill 1. Fibonacci with memoization -- but it crashes on $n=100000$.

map<int, long long> memo;
long long fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

What's wrong?

Stack overflow -- recursion depth is $O(n)$. For large $n$, use bottom-up (iterative) DP or increase the stack size. The memoization itself is fine but the call stack isn't.

Drill 2. 2D DP where dp[i][j] depends on dp[i-1][j] and dp[i][j-1], but results are wrong.

for (int j = 0; j < m; j++)
    for (int i = 0; i < n; i++)
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];

What's wrong?

Out-of-bounds access: when i == 0, dp[i-1][j] is undefined. Need boundary checks or sentinel row/column initialized to 0 (or $-\mathrm{\infty }$ for max problems). Also, the loop nesting is fine here (column-major works), but many people swap it and wonder why -- always check dependency direction.

Drill 3. Counting paths modulo ${10}^9+7$ gives negative numbers.

const int MOD = 1e9 + 7;
dp[0] = 1;
for (int i = 1; i <= n; i++)
    dp[i] = (dp[i-1] - dp[i-2]) % MOD;

What's wrong?

In C++, the % operator can return negative values when the dividend is negative. Fix: dp[i] = ((dp[i-1] - dp[i-2]) % MOD + MOD) % MOD;. This is the single most common modular arithmetic bug in competitive programming.

---

Self-Test

Before moving to practice problems, verify you've internalized the framework -- not just memorized it.

• [ ] Given a new problem, identify the decisions, state, and recurrence systematically using the 4-step process
• [ ] Explain the difference between pull (backward) and push (forward) transitions, and give an example where each is more natural
• [ ] State the two requirements for DP: optimal substructure and overlapping subproblems -- and give a counterexample for each
• [ ] Use the exchange argument to determine if greedy works before resorting to DP
• [ ] Design a DP state for a problem you haven't seen before in under 5 minutes
• [ ] Recognize when a DP state is missing information (getting WA) and add the right dimension to fix it

---

Practice Problems

CF Rating	How This Framework Appears
1200	Recognize "try all subsets" as exponential -> switch to DP
1500	Define 2D states for sequence/grid problems on sight
1800	Add auxiliary dimensions (carry, modular residue, last-action)
2100	Spot when state space can be compressed or transitions optimized with data structures

#	Problem	Archetype	Difficulty	Key idea
1	CF 189A -- Cut Ribbon	Index	CF 1300	Coin change variant
2	CF 1324D -- Pair of Topics	Index	CF 1400	Sort + binary search on DP condition
3	CF 687C -- The Values You Can Make	Sum/Capacity	CF 1500	Track reachable sub-sums within knapsack
4	CF 580D -- Kefa and Dishes	Bitmask	CF 1800	Bitmask + satisfaction bonuses
5	CF 149D -- Coloring Brackets	Interval	CF 1700	Bracket structure + coloring constraints
6	CF 855E -- Salazar Slytherin's Locket	Digit	CF 2000	Count numbers by digit sum in base $b$
7	CF 1092F -- Tree Slicing	Tree	CF 1500	Tree DP on connected components
8	CF 455A -- Boredom	Index	CF 1500	House robber variant on values
9	CF 118D -- Caesar's Legions	Sum/Capacity	CF 1700	3D state: counts + last type
10	CF 1029E -- Tree with Small Distances	Tree	CF 1800	Greedy on tree DP

Progression guide:

• Problems 1-2: warm-up, apply the 4-step process mechanically.
• Problems 3-4: two dimensions, more careful state design.
• Problems 5-7: one from each non-trivial archetype.
• Problems 8-10: require combining ideas or state reduction.

---

Further Reading

Specific DP technique guides in this chapter:

• DP Intro -- 1D Problems -- Foundations of 1D DP with index-based states.
• DP on Sequences -- 2D -- LCS, edit distance, and other two-sequence DPs.
• Knapsack Variants -- 0/1, unbounded, bounded, and counting variants.
• Bitmask DP -- Subset enumeration and permutation problems.
• Interval DP -- Merge/split problems on ranges.
• Digit DP -- Counting numbers with digit constraints.
• Tree DP -- DP on rooted and unrooted trees.
• Convex Hull Trick -- Optimizing linear transitions.
• D&C Optimization -- Optimizing monotone transitions.

---

End of DP Thinking Framework.

---

Solve With Me -- Classic Knapsack Variant (0/1 with Exact Capacity)

Problem: $n$ items each with weight $w_i$ and value $v_i$. Knapsack capacity $W$. Maximize total value with total weight exactly $W$. (If it's impossible to hit exactly $W$, output $-1$.)

My first instinct is greedy -- sort by value-to-weight ratio, grab the best items. But that fails almost immediately. Consider: items $(w=3,v=4)$ and $(w=2,v=3)$ with $W=4$. Greedy picks the ratio-3/2 item first... then can't fill the remaining weight exactly. Meanwhile taking two of the $w=2$ items (if duplicates allowed) gives $v=6$. Even in 0/1 mode, greedy has no way to "undo" a choice that blocks an exact fill.

So why does greedy fail here? Because choosing one item affects which future items can combine to reach exactly $W$. That's the overlapping-subproblems signal. The decision at step $i$ depends on how much capacity remains, and different subsets of earlier items can leave the same remaining capacity.

State: $dp[i][c]$ = best value using items $1..i$ with total weight exactly $c$. Transition: either skip item $i$ ($dp[i-1][c]$) or take it ($dp[i-1][c-w_i]+v_i$, if $c\ge w_i$ and that subproblem is reachable). Base case: $dp[0][0]=0$, everything else is $-\mathrm{\infty }$ (meaning "unreachable"). Answer: $dp[n][W]$, or $-1$ if it's still $-\mathrm{\infty }$.

The tricky bit compared to standard knapsack: initializing to $-\mathrm{\infty }$ instead of $0$. In normal knapsack you allow up to $W$, so $dp[0][c]=0$ for all $c$. Here only $dp[0][0]=0$ is valid because we need exact weight.

Rolled it into 1D: dp[c] scanning $c$ from $W$ down to $w_i$ (standard 0/1 trick to avoid reusing items). Runs in $O(nW)$.

One subtle bug I hit: I forgot to check dp[c - w[i]] != -INF before adding $v_i$. That caused me to "take" items from unreachable states, producing garbage answers. Took me 10 minutes of staring at wrong output on sample 3 before I spotted it.

What to recognize next time: "Exact capacity" changes the DP initialization from all-zeros to only-origin-valid. Greedy fails whenever choices interact -- if you can't evaluate an item in isolation, it's probably DP.

---

Recap

• DP = recursion over overlapping subproblems with optimal substructure. If greedy can't prove local choices are globally safe, think DP.
• 4-step design process: (1) define what dp[...] represents, (2) write the transition, (3) set base cases, (4) determine fill order.
• 6 state archetypes cover most contest DP: index, prefix/suffix, knapsack capacity, interval [l,r], bitmask subset, position-plus-extra.
• State completeness test: can two "different" situations map to the same state? If yes, you are missing a dimension.
• When stuck: check if you need an extra dimension, try thinking top-down first, or reduce to a known archetype.

---

Cross-Links

• DP vs Greedy Guide -- when to choose DP over greedy
• DP State Design Patterns -- advanced state design and reduction
• DP Practice Ladder -- graded problem set