Dynamic Programming — Complete Guide
1. What is DP?
Dynamic Programming is a technique for solving problems by breaking them into
overlapping subproblems, solving each subproblem once, and storing (caching) the result
so it’s never recomputed.
Two properties must hold:
Optimal substructure — the optimal solution to the problem can be built from optimal
solutions to its subproblems.
Overlapping subproblems — the same subproblem is solved again and again if you use
plain recursion.
If a problem has optimal substructure but no overlapping subproblems (each subproblem is
solved once), that’s usually Divide & Conquer, not DP (e.g., merge sort).
2. Why is it used?
Plain recursion on problems with overlapping subproblems leads to exponential blow-up
(e.g., naive Fibonacci is O(2^n)). DP converts this to polynomial time by trading space for
time — you pay memory to store subproblem answers and reuse them.
3. Where is it used?
Optimization problems: min/max cost, min/max profit, longest/shortest sequence
Counting problems: number of ways to do X
Decision problems: can you achieve X? (feasibility)
Real-world: sequence alignment (bioinformatics), shortest paths (Bellman-Ford), text
diff tools, resource allocation, scheduling, compilers (register allocation), speech
recognition (Viterbi), finance (portfolio optimization)
4. How to identify a DP problem — the checklist
Ask these in order:
1. Can I make a recursive brute-force solution? If yes, does it explore a decision tree
(choices at each step)?
2. Do subproblems repeat? Draw the recursion tree mentally for a small input — do you
see the same (state) appearing more than once?
3. Is there a “choose or not choose” / “take this option or that option” structure?
Classic DP smell.
4. Does the problem ask for optimal (min/max), count of ways, or yes/no feasibility —
over some sequence, grid, or set of choices?
5. Can I define the answer to the whole problem in terms of the answer to a smaller
version of itself? (recurrence relation)
If you answer yes to 1, 2, and 4 — it’s DP.
5. Can constraints hint at DP? — YES, this is the single fastest
signal
This is the most reliable “2-minute” trick, especially in competitive programming /
interviews:
Likely
Constraint (n) complexity Hints
expected
n ≤ 20 O(2^n) Bitmask DP
DP over pairs/intervals (e.g. matrix chain,
n ≤ 500 O(n³)
interval DP)
n ≤ 5,000 O(n²) DP over 2 indices
O(n log n) 1D DP, DP + binary search, DP +
n ≤ 10^5–10^6
or O(n) monotonic structure
Target sum / capacity given Classic knapsack-style DP — the target
O(n ×
(e.g. “sum ≤ 10^4”, “weight ≤ size itself becomes a dimension of your
target)
1000”) DP table
Rule of thumb: If the problem gives you two numeric bounds (like n and
target / capacity / W ), and their product is reasonable (≤ ~10^7–10^8), that’s almost a
signature of DP — the second bound is telling you what your second dimension should be.
Also: if brute force is clearly exponential (recursion / all subsets / all partitions) AND n is
small-ish (≤ ~40), that’s DP-or-backtracking-with-memo territory.
6. The “2-minute” pattern triggers (keywords → DP)
Train yourself to pattern-match on phrasing:
“minimum/maximum number of ways”, “count the number of ways”
“minimum cost / maximum profit to reach…”
“longest / shortest subsequence / substring / subarray”
“can you partition / can you make exactly…” (subset sum flavor)
“at each step you can choose…” (decision at every index)
“find if it’s possible to reach the end” with jumps/steps
Grid problems: “paths from top-left to bottom-right”
“edit distance”, “longest common subsequence”
Anything phrased recursively: “f(n) depends on f(n-1) and f(n-2)”
Interval-based: “minimum cost to merge/burst/cut…”
If the problem sounds like “brute force = try every combination/every split point,” and asks
for optimal/count — DP.
7. Intuition / rationale
Think of DP as “smart brute force.” You still consider all possibilities conceptually
(recursion covers the full search space), but:
You cache answers to subproblems (state) so identical work isn’t redone →
memoization (top-down).
Or you build up answers from the smallest subproblem to the largest, in an order that
guarantees dependencies are ready → tabulation (bottom-up).
The core mental model: define a “state” (a small set of parameters that fully describes a
subproblem) and a recurrence (how the answer for a state is built from answers to smaller
states). Everything else is implementation.
8. Types of DP (with recognition patterns)
Type Recognize by Example problems
Answer depends on
Fibonacci, climbing stairs,
1D DP previous 1–2 states in a
house robber
linear sequence
2D DP (grid) Movement/paths on a grid Unique paths, min path sum
Comparing two
2D DP (two sequences) LCS, edit distance
strings/arrays
Item + capacity, each item Subset sum, partition equal
Knapsack (0/1)
used once subset
Unbounded Knapsack Items reusable infinitely Coin change, rod cutting
Matrix chain multiplication,
Choose a split point in a
Interval DP burst balloons, palindrome
range [i, j]
partitioning
Small n (≤ ~20), track
Bitmask DP TSP, assignment problems
subset of used elements
Count numbers with
Count numbers ≤ N with digit
Digit DP property, bounded by a
sum X
number’s digits
Recurrence over a tree’s House robber III, max path sum
Tree DP
children in tree
Explicit “state machine” (e.g. Best time to buy/sell stock with
DP on states/graphs
holding stock or not) cooldown
O(n log n) LIS-style Longest increasing
DP + Binary Search
optimization subsequence
Probability/Expectation
“expected number of…” Dice/board game problems
DP
9. Reusable templates (Java)
Top-down (memoization) — usually the easiest to derive from brute force
import [Link];
import [Link];
class Solution {
Map<Integer, Integer> memo = new HashMap<>(); // key = encoded state
public int solve(int initialState) {
return dp(initialState);
}
private int dp(int state) {
// base case(s)
if (baseCondition(state)) {
return baseValue(state);
}
// already computed?
if ([Link](state)) {
return [Link](state);
}
int best = Integer.MIN_VALUE; // or MAX_VALUE / 0, depending on problem
for (int choice : choicesAvailable(state)) {
int result = compute(choice) + dp(nextState(state, choice));
best = [Link](best, result); // or min/sum
}
[Link](state, best);
return best;
}
}
For multi-dimensional state, use a 2D/3D array as cache instead of a Map (faster), initialized
to a sentinel like -1 :
int[][] memo = new int[n + 1][m + 1];
for (int[] row : memo) [Link](row, -1);
private int dp(int i, int j) {
if (baseCondition(i, j)) return baseValue(i, j);
if (memo[i][j] != -1) return memo[i][j];
int result = /* recurrence using dp(i-1, j), dp(i, j-1), etc. */;
memo[i][j] = result;
return result;
}
Bottom-up (tabulation) — generic 1D
public int solve(int n) {
int[] dp = new int[n + 1];
dp[0] = baseCase0;
dp[1] = baseCase1; // if needed
for (int i = 2; i <= n; i++) {
dp[i] = combine(dp[i - 1], dp[i - 2]); // recurrence
}
return dp[n];
}
Bottom-up — generic 2D (grid / two sequences, e.g. LCS)
public int solve(String a, String b) {
int n = [Link](), m = [Link]();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if ([Link](i - 1) == [Link](j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
0/1 Knapsack template
public int knapsack(int[] weights, int[] values, int capacity) {
int n = [Link];
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]; // don't take item i
if (weights[i - 1] <= w) {
dp[i][w] = [Link](dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}
Space-optimized 1D rolling array (when dp[i] only needs dp[i-1] )
public int knapsackSpaceOptimized(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < [Link]; i++) {
// iterate capacity backwards for 0/1 knapsack (each item used once)
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = [Link](dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
General derivation workflow (use this every time)
1. Write brute-force recursion first (no memo). Get it correct.
2. Identify the state: what varies between recursive calls? (usually index, remaining
capacity/sum, last-taken element, etc.)
3. Add memoization on that state (dict or array cache).
4. If needed, convert to bottom-up for better constants / to avoid recursion depth limits.
5. Optimize space: if dp[i] only depends on dp[i-1] (or last k rows), collapse to rolling
variables.
10. Time & space complexity (generic)
Time ≈ (number of distinct states) × (work done per state)
1D DP: O(n) states × O(1) transition → O(n)
2D DP: O(n·m) states × O(1) transition → O(n·m)
Interval DP: O(n²) states × O(n) transition (trying split points) → O(n³)
Bitmask DP: O(n · 2^n) states × O(n) transition → O(n² · 2^n)
Space ≈ number of states stored, i.e., size of the dp table (can often be reduced by one
dimension via rolling arrays, e.g. O(n·m) → O(m)).
11. Quick self-test flow (do this in your head in ~2 minutes)
1. Read constraints first → does n suggest O(n²), O(n·target), O(2^n)? → strong DP hint.
2. Does the problem ask min/max/count/possible? → DP smell.
3. Can I describe a state with 1–3 variables (index, remaining capacity, last choice) such
that the answer at a bigger state is built from smaller states? → if yes, it’s DP, and you’ve
basically already found your recurrence.
4. If states don’t compress into a few variables (e.g., truly need to remember an entire
arbitrary subset with no small n), it might not be DP — could be greedy, graph, or NP-
hard.