TL;DR
Most LC Hard DP problems fit one of 7 patterns. Identifying the pattern turns a blank-page problem into a template-fill exercise. The hardest part is recognizing which pattern applies — practice that recognition, not memorizing solutions.
Pattern recognition is the real skill in DP — Knapsack, LIS, Grid, Interval, Tree, Bitmask, and Digit DP patterns broken down with examples.In this post, I'll walk through the key concepts with code examples drawn from real production implementations.
Why Patterns Beat Memorization
There are thousands of DP problems. Memorizing solutions doesn't scale. But there are only a handful of structural patterns — and once you recognize the pattern in a new problem, the state definition and transition almost write themselves.
1. 0/1 Knapsack
State: dp[i][w] = best value using first i items with capacity w. Decision: include item i or skip it. Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]).
Recognize it when: you have N items, each with a weight/cost, and a capacity limit. You can only use each item once. Examples: Partition Equal Subset Sum (#416), Target Sum (#494), Last Stone Weight II (#1049).
2. Longest Increasing Subsequence (LIS)
State: dp[i] = length of longest increasing subsequence ending at index i. Transition: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]. O(N²) naturally; reduce to O(N log N) with patience sorting + binary search.
Recognize it when: you need the longest chain of elements satisfying some ordering property. Examples: Number of Longest Increasing Subsequence (#673), Russian Doll Envelopes (#354), Maximum Height by Stacking Cuboids (#1691).
3. Grid / 2D Path
State: dp[r][c] = answer for reaching cell (r,c). Transition: combine values from reachable predecessors (usually up and left). Examples: Unique Paths (#62), Minimum Path Sum (#64), Dungeon Game (#174).
4. Interval / Range DP
State: dp[l][r] = answer for subarray [l..r]. Fill in order of increasing interval length. Transition: try every possible split point k in [l, r-1]. O(N³) typically.
Recognize it when: the answer for a range depends on answers for smaller ranges. Examples: Burst Balloons (#312), Strange Printer (#664), Minimum Cost to Cut a Stick (#1547).
5. Tree DP
State: dp[node][state] — the answer for the subtree rooted at node, given some state at the root. Typically solved with DFS post-order. Examples: House Robber III (#337), Binary Tree Cameras (#968), Maximum Sum BST (#1373).
6. Bitmask DP
State: dp[mask] = answer when the set of items represented by mask have been processed. Transition: try adding each unset bit. O(2^N * N) — only feasible for N ≤ 20.
Recognize it when: N is small (≤ 20) and you need to track a subset of items. Examples: Travelling Salesman, Shortest Superstring (#943), Maximum AND Sum of Array (#2172).
7. Digit DP
Count numbers in range [0, N] satisfying some digit-level constraint. State: dp[pos][tight][...constraint state]. "Tight" tracks whether the current prefix equals the prefix of N (if tight, the next digit is bounded; otherwise it's free).
Recognize it when: you need to count integers in a range with digit constraints. Examples: Count Numbers with Unique Digits (#357), Numbers at Most N Given Digit Set (#902), Non-negative Integers without Consecutive Ones (#600).
Pattern Recognition Cheatsheet
| If you see... | Think... |
|---|---|
| N items, capacity limit, use-once | Knapsack |
| Longest chain / ordering | LIS |
| Grid, path from top-left to bottom-right | Grid DP |
| Subarray / substring, split into two parts | Interval DP |
| Binary tree, subtree values | Tree DP |
| N ≤ 20, all subsets | Bitmask DP |
| Count integers in range with digit properties | Digit DP |
Practice Strategy
Don't practice by grinding random DP problems. Practice by solving one canonical problem per pattern until the state definition comes automatically, then solve 2-3 variants. The skill is pattern recognition — build it deliberately.