Dynamic Programming
⏱ Time: O(N) to O(N * M)💾 Space: O(N) to O(N * M)
Solve complex problems by breaking them down into simpler subproblems, storing results of subproblems to avoid redundant computations (optimal substructure and overlapping subproblems).
🎯 When to Use
- ✓Optimization (minimize / maximize)
- ✓Counting combinations or distinct paths
- ✓Overlapping subproblems and optimal substructure
📝 Pseudocode
Dynamic Programming TemplateO(N) to O(N * M)
1function solveDP(n): 2 dp = Array(n + 1) 3 dp[0] = base_case 4 for i from 1 to n: 5 dp[i] = transition(dp[i - 1], ...) 6 return dp[n]
🏢 Real-World Use Cases
Google Maps
Shortest Route Optimization
Computing multi-stop routing and traffic-cost minimization using dynamic programming algorithms.