Skip to content

Instantly share code, notes, and snippets.

@agconti
Created December 30, 2019 16:29
Show Gist options
  • Save agconti/ad2bc87f59d3ddcde4b99e78618af0cb to your computer and use it in GitHub Desktop.
Save agconti/ad2bc87f59d3ddcde4b99e78618af0cb to your computer and use it in GitHub Desktop.
A gentle intro to dynamic programming!
class Solution_recursive:
"""
Runtime: O(2^n)
Spacetime: O(1)
The classic approach to solving the Fibonacci sequence. The code is elegant but its runtime isn't
very pretty. Its recursive nature necessitates that we calculate some values of f(n) multiple times.
Consider this call graph where duplicated calls are denoted with `~`:
fib(7)
____________|__________
| |
fib(5) fib(6)
_____|_______ ________|________
| | | |
fib(3) fib(4) ~fib(4) ~fib(5)
| | | |
continue... continue... continue... continue...
(( even more duplicate calls as we continue))
The right half of the call graph is a duplicate of the left half after a certain point.
How can we use this knowledge to improve our algorithm?
"""
def fib(self, n):
if n <= 1:
return n
return self.fib(n - 1) + self.fib(n - 2)
class Solution_simple_dynamic_programming_with_cache:
"""
Runtime: O(n)
Spacetime: O(n)
Let's improve the algorithm by caching the left half calls so we don't need to repeat
them on the right half. By adding a cache we've made a tradeoff to improve our runtime
at the expense of our spacetime complexity. This approach systemically improves on the
recursive approach by caching the intermediate results so they are not calculated more than once.
Consider this call graph where duplicated calls are denoted with `~`:
fib(7)
____________|__________
| |
fib(5) fib(6)
_____|_______ ________|________
| | | |
fib(3) fib(4) cache[4] cache[5]
| |
continue... continue...
(( we dont continue the right hand side of the tree because its value is in the cache! ))
"""
cache = {}
def fib(self, n):
if n <= 1:
return n
if n not in self.cache:
self.cache[n] = self.fib(n - 1) + self.fib(n - 2)
return self.cache[n]
class Solution:
"""
Runtime: O(n)
Spacetime: O(1)
We can still improve this algorithm further. We like our new runtime of O(n), but we're less
happy that we're no longer running in constant space. Do we need all of the values stored in our
cache to calculate f(n)? When do we have cache hits?
This is a bottom-up approach that allows us to restrict our cache size to 2 variables giving
us an algorithm that runs in constant space. By going bottom-up, we're able to build the
cache incrementally. In the previous soltuion, we only had cache hits for each value twice. Once
when f(n - 2) equaled our stored value in the cache, and on the next iteration when it happened
again with f(n - 1). These cached values were never read from again. This means that we can
`prune` our cache and keep only the values we need: f(n - 2) and f(n - 1).
This is a good process for working through dynamic programming solutions.
- First identify repeatable subproblems, i.e. the recursive approach
- Next cache intermediate values.
- Finally, prune the cache if you're able.
-- submission stats --
Runtime: 12 ms, faster than 91.53% of Python online submissions for Fibonacci Number.
Memory Usage: 11.8 MB, less than 50.00% of Python online submissions for Fibonacci Number.
"""
def fib(self, n):
if n <= 1:
return n
fib_minus_1 = 1
fib_minus_2 = 0
for _ in range(1, n):
num = fib_minus_1 + fib_minus_2
fib_minus_2, fib_minus_1 = fib_minus_1, num
return num
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment