Top-Down implementation of Dynamic Programming


Memoization stores the values of the function in an array after calculating them, so those values don’t need to be computed again.

Steps from FreeCodeCamp

  1. Make it work (with recursion)
    1. Visualize the problem as a tree
    2. Implement the tree using recursion
    3. Test it
  2. Make it efficient (memoize)
    1. add a memo object to the recursive function argument
    2. add a base case to return memo values
    3. store return values into the memo


Memoization with fibonacci problem.

def fib(int n, memo={})
	if n in memo:
		return memo[n]
	if n <= 2:
		return 1
		memo[n] = fib(n-1, memo) + fib(n-2, memo)
		return memo[n]