[Verse 1] Started with recursion but the call stack's getting deep Same calculations running while my program's losing sleep Zero gives me zero, one returns just one But higher numbers spiral till my memory is done Fibonacci's beauty turned into a curse Exponential time complexity just making things worse Tree of recursive calls spreading way too wide Need a better strategy, gotta optimize my ride [Chorus] Memoize, memorize, save what you compute Store the past results so you don't have to recompute Cache it, stash it, in a table keep it clean Linear time complexity, the fastest you've ever seen Memo-ize, memo-ize, remember what you've done Bottom up or top down, either way you've won [Verse 2] Dictionary in my hand, mapping keys to values tight N maps to fibonacci N, stored throughout the night Check the cache before you calculate, that's the golden rule If it's there just return it, like a computational tool Base cases still important, zero one we handle first Then for every other number, quench that recursive thirst But this time when we call ourselves, we're building up our store Each result gets cached away, so we don't compute no more [Chorus] Memoize, memorize, save what you compute Store the past results so you don't have to recompute Cache it, stash it, in a table keep it clean Linear time complexity, the fastest you've ever seen Memo-ize, memo-ize, remember what you've done Bottom up or top down, either way you've won [Bridge] Two to the power N, that's where we used to be Now it's just O of N, running efficiently Dynamic programming in its purest form Taking exponential chaos, making performance warm Space and time we're trading, memory for speed Overlapping subproblems, memoization's what we need [Verse 3] Top down with recursion plus the memo cache we made Or bottom up iteration, either way the game is played From the smallest problems building up to what we want No repeated calculations, efficiency we flaunt Forty-five fibonacci used to take forever long Now it's instant with our cache, singing optimization's song [Chorus] Memoize, memorize, save what you compute Store the past results so you don't have to recompute Cache it, stash it, in a table keep it clean Linear time complexity, the fastest you've ever seen Memo-ize, memo-ize, remember what you've done Bottom up or top down, either way you've won [Outro] Remember your computations Avoid those duplications Memoized fibonacci Algorithm's lullaby
← Levenshtein distance (edit distance) | Longest common subsequence →