[Verse 1] Started with recursion but it's way too slow Calculating numbers that we already know Stack overflow coming when the input gets high Time complexity exponential making systems cry So we built a cache to store what we computed Hash map holding values so they're not recomputed Bottom up or top down with our memo table Making Fibonacci fast and reliable [Chorus] Memoization saves the day Store the results along the way Base case zero base case one Cache the rest till we are done Linear time instead of tree Space complexity O of n key Remember what we've seen before Fibonacci optimized for sure [Verse 2] Initialize your storage for the sequence chain Dictionary mapping inputs to the values gained Check the cache first before you calculate If it's there return it don't hesitate Recursive calls with lookups in between Most efficient Fibonacci you've ever seen Dynamic programming principle at play Trading space for time in the optimal way [Chorus] Memoization saves the day Store the results along the way Base case zero base case one Cache the rest till we are done Linear time instead of tree Space complexity O of n key Remember what we've seen before Fibonacci optimized for sure [Bridge] From exponential down to linear growth Overlapping subproblems we can control both West coast optimization with the cleanest flow Memo table working everywhere we go [Verse 3] Top down approach with recursive design Or bottom up iterative building the line Either way the cache is what makes it shine Avoiding redundant work by design Interview question classic but you got the skill Memoized solution climbing up the hill Time and space tradeoffs that you understand Fibonacci sequence optimized by your hand [Chorus] Memoization saves the day Store the results along the way Base case zero base case one Cache the rest till we are done Linear time instead of tree Space complexity O of n key Remember what we've seen before Fibonacci optimized for sure [Outro] Cache it memo it optimize the code Dynamic programming on the golden road
← Levenshtein distance (edit distance) | Longest common subsequence →