Trees, graphs and optimization
Dynamic programming
Reuse solutions to repeated subproblems.
Understand the problem
Define the state in a sentence, write a transition, state base cases, and choose an evaluation order. Optimize memory only after the recurrence is correct.
Make it concrete
dp[i] for word break is true if some valid prefix dp[j] is followed by a dictionary word s[j:i].
Trade-offs and pitfalls
A small-looking recurrence may still have costly substring or transition operations.
Check your understanding
Derive a recurrence for minimum coins when denominations are reusable.
Practice this topic