Internship← Coding Interview Prep (LeetCode) learning pathCoding Interview Prep (LeetCode) · Module 9 of 10
Dynamic programming
DP solves problems by combining answers to smaller overlapping subproblems.
📖 Key ideas
- Look for optimal substructure and overlapping subproblems.
- Memoisation caches recursive results (top-down).
- Tabulation fills a table from small to large (bottom-up).
- Classic problems: climbing stairs, house robber, coin change, longest common subsequence, knapsack.
- Define the state, the transition and the base case.
💡 Real-life example: Like remembering multiplication tables: once you know 6 x 7, you reuse it instead of adding 6 seven times again.
MemoisationCache results of recursive calls
TabulationFill a DP table bottom-up
StateWhat a subproblem represents
TransitionFormula linking states