Lesson 28.4 · DP Foundations: 1D
Recognising a DP Problem
Count the ways, find the min or max, or decide yes or no over choices that interact, especially when greedy fails and brute force branches exponentially.
8 min
Think of it like this
A sat-nav that knows the best route from every junction to your destination: the best route from here is just one step plus the best route from the next junction.
1.Signals
Words like "number of ways", "minimum cost", "maximum profit", "can you reach / form" over a sequence of choices. A brute-force recursion that branches at every step. A small counterexample that breaks the obvious greedy choice.
Not DP: when a greedy choice is provably safe (intervals, Module 33), or when the subproblems don't overlap (merge sort is divide and conquer, each half solved once).
Where the following modules take it: grids (state is a cell), knapsack (state includes remaining capacity), two sequences (state is a pair of indices), intervals (state is a range), bitmasks (state is a set).
Remember
- Ways / min / max / possible.
- Exponential recursion with repeats.
- Greedy counterexample → think DP.
Common mistakes
- Forcing DP onto problems where a greedy proof exists (slower and harder to write).