Dynamic programming feels enormous because it is usually taught as a technique rather than a catalogue. In practice, the overwhelming majority of DP problems you will meet are one of about eight state designs. Learning them by shape is far more useful than learning twenty problems by name.
First: what a state has to be
A DP state is a description of a subproblem complete enough that the answer depends on nothing outside it. If you find yourself needing information the state does not carry, the state is wrong — that is the actual work, and the recurrence usually falls out once the state is right.
1. Linear scan on one index
State: dp[i] = the answer considering the first i elements. Used for house robber, climbing stairs, maximum subarray, decode ways.
2. Index plus a small mode
State: dp[i][k] where k is a tiny enumeration — holding or not holding, used or unused, count of transactions so far. Used for stock problems with cooldowns or transaction limits.
3. Two sequences
State: dp[i][j] over prefixes of two inputs. Used for edit distance, longest common subsequence, regular expression matching, interleaving strings.
4. Knapsack
State: dp[i][w] = best value using the first i items with capacity w. The one-dimensional rolling version is the version worth memorising, including the direction of the inner loop — descending for 0/1, ascending for unbounded.
Iterating the capacity ascending in 0/1 knapsack silently allows reusing an item, turning it into the unbounded variant. The loop direction is the whole difference.
5. Interval DP
State: dp[i][j] over a contiguous range, built by increasing length and split at every interior point. Used for matrix chain multiplication, burst balloons, palindromic partitions.
6. Bitmask over subsets
State: dp[mask] or dp[mask][i], where mask records which elements are used. Only viable for n up to about 20. Used for travelling salesman, assignment problems, partitioning into k groups.
7. Digit DP
State: position in the number, whether the prefix is still tight against the bound, plus whatever the problem tracks. Used for counting numbers below N with a property.
8. DP on a tree
State: dp[node][mode] combined from children in post-order. Used for tree diameter, independent set on a tree, distributing coins.
Memoisation first, tabulation second
Write the recursive version with a cache first. It is closer to how you reasoned about the problem, it makes the state explicit in the function signature, and it only visits reachable states. Convert to a bottom-up table afterwards, if you need the constant factor or want to drop a dimension. Going straight to tabulation is how people end up with a table whose indices they cannot explain.
The honest caveat
This catalogue covers most of what you will meet, not all of it. The genuinely hard DP problems are hard precisely because the state is not one of these — and no amount of memorising shapes substitutes for being able to ask what the subproblem actually needs to know.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.