Summary
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).