Dynamic Programming
Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into overlapping subproblems. It solves each subproblem once and caches the result (memoization or tabulation) to prevent redundant recalculations.
Why It Exists
Standard recursion can calculate identical subproblems repeatedly, resulting in exponential O(2^N) runtimes. DP caches duplicate calculations, reducing runtimes to linear or portfolio scales.
Intuition for Beginners
“If I ask you what 1 + 1 + 1 + 1 + 1 is, you count and say 5. If I add another '+ 1' to the end, you don't recount from the start; you remember 5 and add 1 to get 6. Remembering past results is the core of DP.”
Visual Explanation
Recursive duplicate tree vs. DP linear memoization:
Fib(4) Fib(4) [Calculates once]
/ \ / \
Fib(3) Fib(2) Fib(3) Fib(2) [Fetched from cache]
/ \ /
Fib(2) Fib(1) Fib(2)Complexity Analysis
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Naive Recursion | O(2^N) | O(N) | Duplicate sub-calls grow exponentially |
| Memoization | O(N) | O(N) + O(N) | Top-down: recursion stack + cache hash |
| Tabulation | O(N) | O(N) | Bottom-up: iterative array table |
| Space Optimized | O(N) | O(1) | Maintain only last two states |
Production & Real World Applications
- •Git Diff: Longest Common Subsequence (LCS) algorithm comparing text changes.
- •Routing Routers: Computing shortest path transitions dynamically.
Algorithmic Patterns
Adding cache registers inside recursive functions to intercept duplicate calculations.
Filling an array iteratively from base cases up to target index limits.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Not identifying the correct base cases.
- ⚠️Overallocating table space when only the last few indices are needed (wastes memory).