I spent three weeks "studying" dynamic programming before my campus placements by going through solved problems one by one. I could reproduce solutions I'd seen. But put a new problem in front of me and I was lost. Sound familiar?

The breakthrough came when I stopped asking "how do I solve this?" and started asking "which pattern does this belong to?" There are really only a handful of underlying DP structures. Once you see them, new problems stop feeling new.

First: The Three Questions You Always Ask

Before you write a single line of DP code, answer these:

What's the state? What information do you need to uniquely describe a subproblem? Usually 1-2 variables (index, remaining capacity, etc.)
What's the recurrence? How does the answer to a bigger problem depend on smaller ones? This is the real insight — everything else is mechanics.
What are the base cases? The smallest problems you can solve directly, without recursion.

If you can answer all three clearly, you can code any DP problem. The patterns below just help you find those answers faster.

Pattern 1: Knapsack (0/1 and Unbounded)

The canonical problem: you have items with weights and values, and a bag with limited capacity. Maximize value without exceeding capacity.

State: dp[i][w] = max value using first i items with capacity w. Recurrence: either take item i or don't. Variations include the unbounded knapsack (use an item multiple times) and the subset sum problem (can we hit exactly this target weight?).

Recognition signals: "given a set of items, find the best combination within some constraint." Partition Equal Subset Sum, Target Sum, Coin Change — all knapsack variants underneath.

Pattern 2: Fibonacci-Style (Linear DP)

Problems where each state depends on a fixed number of previous states. Climbing Stairs, House Robber, Jump Game, Decode Ways.

The recurrence looks like f(n) = f(n-1) + f(n-2) or some variation. These are often the most approachable DP problems, but they still require careful thought about what "state" means in context. In House Robber, for example, the state isn't just position — it implicitly encodes whether you robbed the previous house.

Pattern 3: Longest Common Subsequence (Grid DP)

Given two sequences, find their longest common subsequence (or substring, or edit distance). State: dp[i][j] = answer considering first i characters of string A and first j characters of string B.

This pattern is used in git diff (comparing file versions), DNA sequencing tools, and plagiarism detection. Problems like Edit Distance and Shortest Common Supersequence are direct relatives.

Pattern 4: Palindromes and Interval DP

State is a range [i, j] of the input, and you're solving for that interval. Longest Palindromic Subsequence, Burst Balloons, and Matrix Chain Multiplication all fit here.

The trick with interval DP: you solve smaller intervals first (length 1, then 2, then 3...) and build up to the full range. The order of computation matters.

Pattern 5: DP on Trees and Graphs

State is a node (or a node + some property), and recurrence is defined over children or neighbors. House Robber III (on a tree), Binary Tree Maximum Path Sum, and Minimum Height Trees all involve DP where the "subproblems" are subtrees.

This one feels different from the others because the "order" of computation is defined by the tree structure itself — you process children before parents (post-order traversal), and that becomes your bottom-up DP order.

How to Practice This Way

When you encounter a new DP problem, before looking at any solution, try to categorize it. Is there a capacity constraint? (Knapsack.) Two sequences being compared? (LCS.) A range that needs to be solved optimally? (Interval.) Linear dependency on recent states? (Fibonacci-style.)

You'll misclassify sometimes. That's fine — the misclassification is where the learning happens. Over time you'll develop an instinct for it, and that instinct is what gets you through problems you've genuinely never seen before.

Stop Memorizing DP Problems — Learn the 5 Core Patterns Instead