MainExamplesHistoryRecommended Reading
Dynamic Programming (DP) is a problem-solving technique that breaks complex problems into smaller subproblems and stores their solutions to avoid recomputing them. It's like solving a jigsaw puzzle: once you figure out how to fit a piece, you remember it instead of trying again.
The Key Idea:
- Break down: Divide problem into smaller subproblems
- Store solutions: Remember answers to subproblems (memoization)
- Reuse: Use stored solutions instead of recalculating
- Build up: Solve bigger problems using smaller solutions
When to Use DP:
- Overlapping subproblems: Same subproblems appear multiple times
- Optimal substructure: Optimal solution contains optimal solutions to subproblems
- Examples: Fibonacci, shortest path, knapsack problem
Approaches:
- Top-down: Recursive with memoization (start from the problem, work down)
- Bottom-up: Iterative, build from smallest to largest
Classic Example - Fibonacci:
Without DP: Calculate fib(5) recalculates fib(3) multiple times With DP: Calculate once, store it, reuse it
FAQ
What's the difference between DP and divide-and-conquer?
Divide-and-conquer breaks problems into independent subproblems. DP solves overlapping subproblems and stores solutions.
Is DP always better?
No! DP adds memory overhead. Use it when subproblems overlap. Simple recursion might be fine for non-overlapping problems.