Training Trains Internship
Student login
← Algorithm Design learning path
Algorithm Design · Module 4 of 10

Dynamic programming

Solve overlapping subproblems once and reuse results.

📖 Key ideas

  1. DP applies when subproblems overlap and optimal substructure exists.
  2. Memoisation: top-down recursion with caching.
  3. Tabulation: bottom-up table filling.
  4. Classic problems: Fibonacci, 0/1 knapsack, LCS, edit distance, coin change, matrix chain.
  5. Define state, transition and base cases.
💡 Real-life example: DP is writing answers in a notebook so you never solve the same sum twice.
MemoisationCaching recursive results
TabulationBottom-up table
StateParameters describing a subproblem
TransitionHow states relate