Dynamic programming has a reputation for being the hardest topic in competitive programming. I used to agree with that.
Then I realised something: most DP problems aren't unique. They're variations on about six core patterns. Once you internalise those patterns, you stop treating each DP problem as a new puzzle and start asking: "which pattern is this?"
This post breaks down the six patterns I keep coming back to. For each one, I'll explain the core idea, show a simple example in C++, and point you to a representative problem to practice.
Pattern 1: Linear DP (1D State)
Core idea: The answer for position i depends only on answers at earlier positions.
This is the most foundational pattern — the building block everything else extends from.
Classic example: Longest Increasing Subsequence
int lis(vector<int>& a) {
int n = a.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
return *max_element(dp.begin(), dp.end());
}
dp[i] = length of the longest increasing subsequence ending at index i. To find dp[i], look at every earlier element that's smaller and take the best.
When to recognize it: The problem involves a sequence, and the answer for each element depends on some subset of previous elements.
Practice: Codeforces 340E, LeetCode 300
Pattern 2: Grid DP (2D State)
Core idea: State is a position (i, j) on a grid. Transitions come from adjacent cells — usually up and left.
Classic example: Minimum Path Sum
int minPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
dp[0][0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
int best = INT_MAX;
if (i > 0 && dp[i-1][j] != INT_MAX) best = min(best, dp[i-1][j]);
if (j > 0 && dp[i][j-1] != INT_MAX) best = min(best, dp[i][j-1]);
dp[i][j] = best + grid[i][j];
}
}
return dp[m-1][n-1];
}
When to recognize it: Grid, matrix, or 2D table. Movement is restricted (usually right/down only). Count paths, minimize cost, maximize value.
Practice: Codeforces 166E, LeetCode 64
Pattern 3: Knapsack DP
Core idea: You have items with weights and values. You can pick or not pick each item. Maximize value subject to a capacity constraint.
This pattern is deceptively broad — "knapsack thinking" applies to many problems that don't look like packing bags.
Classic 0/1 Knapsack:
int knapsack(int W, vector<int>& wt, vector<int>& val) {
int n = wt.size();
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]; // don't take item i
if (wt[i-1] <= w)
dp[i][w] = max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1]); // take it
}
}
return dp[n][W];
}
Key variants to know:
- 0/1 Knapsack — each item can be taken at most once
- Unbounded Knapsack — each item can be taken unlimited times (coin change)
- Subset Sum — can we reach exactly target weight?
When to recognize it: "Select items/elements, subject to a total limit, maximize/minimize something."
Practice: Codeforces 459B, LeetCode 416 (Subset Sum variant)
Pattern 4: Interval DP
Core idea: State is a subarray or subrange [l, r]. To solve [l, r], you split it at some midpoint k and combine the answers for [l, k] and [k+1, r].
This pattern shows up in matrix chain multiplication, burst balloons, palindrome partitioning, and similar problems.
Classic example: Minimum Cost to Merge Stones
The general structure looks like this:
// dp[l][r] = optimal answer for subarray [l..r]
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] + cost(l, r));
}
}
}
Notice the iteration order: solve smaller intervals first, then larger ones. This ensures that when you compute dp[l][r], dp[l][k] and dp[k+1][r] are already solved.
When to recognize it: The problem involves a sequence, and the optimal solution for a range depends on splitting it somewhere.
Practice: Codeforces 149D, LeetCode 1000
Pattern 5: DP on Trees
Core idea: State is a node. You compute the answer for a subtree rooted at each node using the answers of its children.
// Standard tree DP template
void dfs(int node, int parent) {
dp[node] = base_value;
for (int child : adj[node]) {
if (child == parent) continue;
dfs(child, node);
dp[node] = combine(dp[node], dp[child]);
}
}
Classic example: Maximum Independent Set on a Tree
For each node, consider two states: include the node in the set, or exclude it.
// dp[v][0] = max independent set in subtree of v, v NOT included
// dp[v][1] = max independent set in subtree of v, v included
void dfs(int v, int p) {
dp[v][1] = 1; // include v
dp[v][0] = 0; // exclude v
for (int u : adj[v]) {
if (u == p) continue;
dfs(u, v);
dp[v][1] += dp[u][0]; // if v included, children must be excluded
dp[v][0] += max(dp[u][0], dp[u][1]); // if v excluded, children can go either way
}
}
When to recognize it: The problem is on a tree. Answers propagate from leaves to root. Subtrees are independent.
Practice: Codeforces 161D, LeetCode 337
Pattern 6: Bitmask DP
Core idea: State includes a bitmask representing a subset of elements. Used when n is small (usually ≤ 20) and you need to track which elements have been used.
Classic example: Travelling Salesman Problem
// dp[mask][i] = min cost to visit all cities in mask, ending at city i
int n = cities.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0; // start at city 0
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u))) continue;
if (dp[mask][u] == INT_MAX) continue;
for (int v = 0; v < n; v++) {
if (mask & (1 << v)) continue;
int next_mask = mask | (1 << v);
dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
}
}
}
The bitmask mask tracks which cities have been visited. mask & (1 << i) checks if city i is in the set.
When to recognize it: Small n (≤ 20). You need to track which elements have been selected or visited. "Optimal assignment" or "cover all elements" problems.
Practice: Codeforces 327E, LeetCode 847
How to Actually Use These Patterns
Knowing the patterns isn't enough. You need to practice recognizing them before you can apply them under contest conditions.
My approach:
- Pick one pattern at a time
- Solve 8–10 tagged problems for that pattern — easy to medium difficulty
- After each problem, write down in plain English: "this was a [pattern] problem because..."
- Only move to the next pattern when you can identify the current one within 2–3 minutes of reading a problem
The recognition is the hard part. The coding, once you see the pattern, is usually mechanical.
One more thing: write your own transitions from scratch each time. Don't copy templates. The act of re-deriving the state definition and transition yourself is what builds the intuition. Templates make you fast but fragile — you want to be slow and robust first.
Summary
| Pattern | State | Key Question |
|---|---|---|
| Linear DP | dp[i] |
What's the best ending at position i? |
| Grid DP | dp[i][j] |
What's the best to reach cell (i,j)? |
| Knapsack | dp[i][w] |
What's the best using first i items with capacity w? |
| Interval DP | dp[l][r] |
What's the best for subrange [l,r]? |
| Tree DP | dp[v] |
What's the best for the subtree rooted at v? |
| Bitmask DP | dp[mask][i] |
What's the best having visited the set mask, last at i? |
These six patterns won't cover every DP problem you'll ever see. But they'll cover most of them — and more importantly, they'll give you a framework for thinking about the ones that don't fit neatly.
I'm Animesh, a CS final year student and competitive programmer. Follow along for more algorithm breakdowns and CP content.
Top comments (0)