Context
When facing recursive problems we quickly identify the memorization enhancement to avoid wasting cycles for past computations. But what about the underlying implementations top-down vs bottom-up?
In the video below I am comparing these two. And the drawbacks of using BFS in this particular case:
- Higher memory usage due to maintaining a queue and a visited set.
- Worse than DP for large amount values (since BFS explores level by level, it can be slow for high values).
Summary
Visual representation
Comparisson
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Recursive DP (Top-Down w/ Memoization) | O(amount × len(coins)) | O(amount) | Efficient, but recursion uses stack memory |
| Iterative DP (Bottom-Up) | O(amount × len(coins)) | O(amount) | Best for dense subproblem coverage |
| BFS (Graph Traversal) | O(amount × len(coins)) (Worst case) | O(amount) | Can be more efficient for small values |
Top comments (0)