Blind 75 — Dynamic Programming Pattern Guide

How to Identify a “DP” Problem

Interview Triggers

• “Count the number of ways…”
• “Find the minimum / maximum cost / steps…”
• “Is it possible to…”
• Overlapping subproblems + optimal substructure
• A choice at each step (take / skip, left / right, include / exclude)
• Recursive brute force has obvious exponential repetition

Which Sub-Pattern Does It Belong To?

If the problem looks like…	Use this DP style	Example LC
Stairs / Fibonacci / state depends on prev 1-2	1-D linear DP	70
“Pick coins to make amount” (unlimited supply)	Unbounded knapsack	322
“Longest subsequence with property”	1-D nested DP or patience sort	300
“Longest common between two strings”	2-D DP grid	1143
“Split string into dictionary words”	1-D DP + HashSet lookup	139
“Count combinations that sum to target” (order matters)	1-D permutation DP	377
Adjacent constraint (no two neighbors)	State-machine DP (take/skip)	198, 213
Decode digits → letters	1-D DP with 1-digit/2-digit branch	91
Grid path counting	2-D grid DP	62
“Can you reach end?” / max reach	Greedy reachability (not DP)	55

---

The Decision Tree

DP PROBLEM
│
├─ Linear sequence, state depends only on prev k?
│   ├─ Fibonacci-like                    → 1-D DP (LC 70)
│   ├─ Adjacent-skip                     → State machine (LC 198, 213)
│   └─ Subsequence with property         → Nested 1-D DP (LC 300)
│
├─ Knapsack-style (capacity / target)?
│   ├─ Pick each item ≤ 1 time           → 0/1 knapsack
│   └─ Unlimited use                     → Unbounded (LC 322, 377)
│
├─ Two sequences interacting?
│   └─ 2-D DP[i][j]                      → LCS (LC 1143)
│
├─ Grid / matrix?
│   └─ 2-D DP (paths, min cost)          → LC 62
│
├─ String partition / substring DP?
│   └─ 1-D DP indexed by prefix length   → LC 139, 91
│
└─ Reachability with no "best" to compute?
    └─ Greedy, not DP                     → LC 55

---

The Universal DP Recipe

1. Define the state: “Let dp[i] = the answer for the subproblem ending / starting at index i.”
2. Define the transition: write dp[i] in terms of dp[i-1], dp[i-2], etc.
3. Define the base case: dp[0] = ?
4. Iteration order: bottom-up (loop forward) or top-down (memoized recursion)
5. Final answer: usually dp[n] or dp[n-1] or max(dp)
6. Optimize space: many 1-D DPs only need O(1) variables

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	DP Style
1	Climbing Stairs	70	Easy	1-D Fibonacci
2	House Robber	198	Medium	State machine
3	House Robber II	213	Medium	Circular 198
4	Coin Change	322	Medium	Unbounded knapsack
5	Unique Paths	62	Medium	2-D grid
6	Jump Game	55	Medium	Greedy reachability

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	DP Style
1	Longest Increasing Subsequence	300	Medium	Nested 1-D / patience
2	Longest Common Subsequence	1143	Medium	2-D DP
3	Word Break	139	Medium	1-D DP + HashSet
4	Combination Sum IV	377	Medium	1-D permutation DP
5	Decode Ways	91	Medium	1-D with branch

---

Java Implementation Tips

• Prefer int[] over Integer[] for DP tables (no autoboxing).
• Initialize “min” DP arrays with Integer.MAX_VALUE and dp[0] = 0; check overflow before adding 1.
• For “amount + 1” sentinel (LC 322), use amount + 1 not Integer.MAX_VALUE to avoid overflow on +1.
• Top-down: use Map<State, Integer> or Integer[] (so null = unvisited).
• Bottom-up with space optimization: replace dp[] with two variables prev, curr.

---

Senior Mental Trigger

“What is the smallest piece of the answer I can compute? Now express the bigger answer in terms of smaller pieces.”