How to Recognize DP Problems in 10 Seconds
Dynamic programming problems can feel intimidating, but they share telltale signs. If you can spot these signals in the first 10 seconds of reading a problem, you will know to reach for DP instead of brute force or greedy. This guide covers the three core signals, the keywords that scream DP, and a brief intro to each major DP sub-pattern.
The 3 Signals That Indicate DP
Signal 1: Optimal Substructure
The optimal solution to the whole problem can be built from optimal solutions to smaller subproblems. If the best path from A to C goes through B, then the segment from A to B must be optimal for that subpath. Ask yourself: "If I knew the answer for a smaller input, could I combine it to get the answer for the larger input?" If yes, you have optimal substructure.
Example: Climbing Stairs — The number of ways to reach step n equals the sum of ways to reach step n-1 and step n-2. The subproblems combine additively.
Signal 2: Overlapping Subproblems
The same subproblem is solved multiple times in a naive recursive solution. A recursive tree would show repeated branches. DP avoids recomputation by storing results in a table. If you draw out the recursion and see the same subproblem appearing again and again, that is overlapping subproblems.
Example: Fibonacci — fib(5) requires fib(3) twice and fib(2) three times. Memoization or tabulation eliminates redundant work.
Signal 3: Counting or Optimization Phrasing
The problem asks for a count ("how many ways", "number of distinct") or an optimization ("maximum", "minimum", "longest", "shortest"). These goals naturally fit a recurrence: you define a state and combine subproblem answers with max, min, or sum.
Example: "Find the minimum number of coins to make amount", "How many ways to decode this string?"
Keywords That Signal DP
When you see these words in a problem statement, DP should be on your radar:
- Counting: "how many ways", "number of", "count", "distinct"
- Optimization: "maximum", "minimum", "longest", "shortest", "best", "optimal"
- Substructure: "subsequence", "substring" (sometimes), "subset", "partition"
- Decisions: "choose", "pick", "take or skip", "include or exclude"
- Constraints: "capacity", "weight", "amount", "limit"
DP Sub-Patterns at a Glance
Fibonacci Pattern
Each state depends only on the previous 1–2 states. Recurrence looks like dp[i] = f(dp[i-1], dp[i-2]). Space can be optimized to O(1). Classic problems: Climbing Stairs, House Robber, Decode Ways.
0/1 Knapsack Pattern
For each item, you choose take or skip. One item, one decision. Capacity constraint. Iterate weights in reverse for 1D optimization. Classic problems: Partition Equal Subset Sum, Target Sum, 0/1 Knapsack.
View 0/1 Knapsack Pattern →Unbounded Knapsack Pattern
Same as 0/1 but items can be reused. Iterate amounts in forward direction. Classic problems: Coin Change, Coin Change II, Perfect Squares.
View Unbounded Knapsack Pattern →LCS (Longest Common Subsequence) Pattern
Two sequences, 2D DP. Each cell compares prefixes. Recurrence: match or skip from either string. Classic problems: Longest Common Subsequence, Edit Distance, Longest Palindromic Subsequence.
View LCS Pattern →DP on Trees
Tree structure + optimization. Post-order DFS. Each node computes from children. Often track both "extendable" and "through-node" answers. Classic problems: Binary Tree Maximum Path Sum, House Robber III, Diameter of Binary Tree.
View DP on Trees Pattern →Grid DP
2D grid with a traversal goal. Each cell depends on the cell above and/or to the left. Often optimizable to 1D space. Classic problems: Unique Paths, Minimum Path Sum, Maximal Square, Dungeon Game.
View Grid DP Pattern →The 10-Second Checklist
1. Does the problem ask for a count or optimization (max/min)?
2. Can the answer be built from smaller subproblem answers?
3. Would a naive recursive solution repeat the same subproblems?
If all three are yes, think DP. Then use our Decision Tree to narrow down which sub-pattern.
Related reads:
Master all DP patterns
AlgoArk has animated walkthroughs for Fibonacci, Knapsack, LCS, DP on Trees, and more.
Browse All Patterns