Dynamic programming
Overview
Dynamic programming divides a problem into overlapping subproblems and stores results to avoid recomputation.
Common DP questions
- Fibonacci
- Climbing stairs
- House robber
- Coin change
- Longest increasing subsequence
- Word break
- Unique paths
- Edit distance
- Partition equal subset sum
DP states
- 1D DP
- 2D DP
- memoization
- tabulation
Interview guidance
If the same subproblem occurs repeatedly, DP is often the right direction.
Can you explain it without the notes?
Dynamic programming
Use your own words. Explain an example and one limitation before checking the explanation.
Check your explanation
What it is
Turn this concept into a clear answer.
Practice this conceptAdapted from 14_DSA_MASTER.md · “11. Dynamic programming”. Examples are study fragments; framework behavior can depend on your version.