Internship← Competitive Programming learning pathCompetitive Programming · Module 8 of 10
Dynamic programming
Store answers to overlapping subproblems.
📖 Key ideas
- DP = recursion + memory: solve each subproblem once.
- Define the state, the transition and the base case.
- Top-down uses memoisation; bottom-up fills a table.
- Classics: Fibonacci, 0/1 knapsack, LIS, LCS, coin change.
- Complexity = number of states x work per state.
💡 Real-life example: DP is writing answers in a notebook so you never solve the same homework question twice.
StateParameters describing a subproblem
TransitionHow a state uses smaller states
MemoisationCaching recursive results
TabulationBottom-up table filling