DP Theory
Table of Contents
Dynamic Programming
Dynamic Programming is Recursion without repetition
Top Down memoization:
- Store the value in hashmap to avoid repeating the same function call. A computed subproblem value for the key is stored in the hashmap
memorandumlatin word means to remember, it is calledmemoization- Memo version of fib:
def fib(n):
memo[0] = 0
memo[1] = 1
if n in memo:
return memo[n]
memo[n] = fib(n-1) * fib(n-2)
return memo
References:
Interview Kickstart: