Dynamic Programming

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

Feb 14, 2025 - 12:09

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