Dynamic Programming Patterns

Pattern / Category	Typical Question Types	Keywords in Question	Why Use / Notes
1D DP (Linear) – Common	Max sum subarray, Min cost, Steps	maximum, minimum, steps	Recurrence based on previous state; linear array DP; universal for arrays/DP
2D DP – Common	Matrix path sum, Grid problems	grid, matrix, path	DP table based on neighbors; universal for matrices/grids
Knapsack / Subset Sum – Common	Weight/value optimization	capacity, weight, max value	Classic optimization problem; track best value for given capacity
Unbounded Knapsack – Rare / Bonus	Infinite item selection	weight, value, repeat	Can pick items multiple times; DP similar to knapsack but with repetition
Longest Increasing Subsequence (LIS) – Common	LIS, sequence problems	increasing, subsequence	Track subsequences using DP or patience sorting; common interview problem
DP on Trees – Common	Max path sum, Diameter, Rob houses	child, subtree, parent	Post-order traversal DP; tree-specific patterns
DP with Memoization – Common	Recursive problems	cache, recursion, overlapping	Avoid recomputation; recursive approach with memoization
State Machine DP – Rare / Bonus	String parsing, Automata	state, transition	Track multiple states over steps; used for strings, automata, or parsing DP
Probability / Digit DP – Rare / Bonus	Probability, counting	probability, digits	Model probabilistic events; count sequences or digit constraints
Bitmask DP – Rare / Bonus	Traveling salesman, Subset problems	subset, mask, state	Encode subset states as bits; ideal for TSP or combinatorial subset DP
Matrix Chain Multiplication (MCM) – Rare / Bonus	Optimal multiplication order	matrices, cost	DP over intervals; find minimal multiplication cost for sequence of matrices

---

Dynamic Programming – Detection & Usage Guide

Rarity Legend:

• Common / Very Common – Appears frequently in interviews; must know deeply.
• Rare / Bonus – Appears occasionally or in advanced contests; important for specialized DP problems.

---

1. 1D DP (Linear) – Common

When to use / Detection cues:

• Input: Linear array or sequence.
• Keywords: maximum, minimum, steps.
• Hints: Each state depends on previous state(s); optimize sum, cost, or steps.
• Typical questions: Max sum subarray, Min cost path in array, Step/ladder problems. Mental trigger: “Linear sequence” + “previous step/state dependency”.

---

2. 2D DP – Common

When to use / Detection cues:

• Input: Matrix or grid.
• Keywords: grid, matrix, path.
• Hints: Recurrence based on neighboring cells (up, left, diagonals).
• Typical questions: Grid unique paths, Max path sum, Min path cost. Mental trigger: “Matrix/grid” + “neighbor dependency”.

---

3. Knapsack / Subset Sum – Common

When to use / Detection cues:

• Input: Array of weights/values and capacity.
• Keywords: capacity, weight, max value.
• Hints: Optimize value under weight constraints.
• Typical questions: 0/1 Knapsack, Subset sum problem, Max value with weight limit. Mental trigger: “Optimize sum/value under capacity constraint”.

---

4. Unbounded Knapsack – Rare / Bonus

When to use / Detection cues:

• Input: Array of weights/values; items can repeat.
• Keywords: repeat, infinite, weight, value.
• Hints: Like knapsack but can take items multiple times.
• Typical questions: Coin change (min coins), Max value with unlimited items. Mental trigger: “Can pick items multiple times”.

---

5. Longest Increasing Subsequence (LIS) – Common

When to use / Detection cues:

• Input: Array or sequence.
• Keywords: increasing, subsequence.
• Hints: Find max-length increasing subsequence; patience sorting possible.
• Typical questions: LIS length, Max sum increasing subsequence, Constrained subsequences. Mental trigger: “Sequence increasing / subsequence problem”.

---

6. DP on Trees – Common

When to use / Detection cues:

• Input: Tree / hierarchical structure.
• Keywords: child, parent, subtree.
• Hints: Post-order traversal DP to solve for max/min path, sum, or other subtree properties.
• Typical questions: Max path sum in tree, Rob houses problem, Diameter of tree. Mental trigger: “Tree input” + “compute value from children upwards”.

---

7. DP with Memoization – Common

When to use / Detection cues:

• Input: Any structure with recursive overlapping subproblems.
• Keywords: cache, recursion, overlapping.
• Hints: Recursive solution with caching to avoid recomputation.
• Typical questions: Fibonacci, Recursive grid paths, Recursive knapsack. Mental trigger: “Recursion with overlapping subproblems”.

---

8. State Machine DP – Rare / Bonus

When to use / Detection cues:

• Input: String, automata, or stepwise transitions.
• Keywords: state, transition.
• Hints: Track multiple states over steps; DP table stores state at each step.
• Typical questions: String parsing, Regular expression matching, Automata simulation. Mental trigger: “Stepwise transitions / state tracking”.

---

9. Probability / Digit DP – Rare / Bonus

When to use / Detection cues:

• Input: Counting/probability problem, often with digits or sequences.
• Keywords: probability, digits.
• Hints: Model event probability or count sequences; DP table tracks state probabilities.
• Typical questions: Count numbers with constraints, Probability of events, Digit DP problems. Mental trigger: “Count / probability” + “DP table to track states”.

---

10. Bitmask DP – Rare / Bonus

When to use / Detection cues:

• Input: Small n (≤20), subsets or combinatorial states.
• Keywords: mask, subset, state.
• Hints: Encode subset states as bits; iterate 0..2^n-1.
• Typical questions: Traveling salesman problem, Subset sum with constraints, Task assignment problems. Mental trigger: “Subset / mask / combinatorial DP”.

---

11. Matrix Chain Multiplication (MCM) – Rare / Bonus

When to use / Detection cues:

• Input: Sequence of matrices.
• Keywords: matrices, cost.
• Hints: DP over intervals to find optimal multiplication order.
• Typical questions: Optimal matrix multiplication order, Minimize scalar multiplications. Mental trigger: “Sequence of matrices” + “interval optimization”.