Top-Down implementation of Dynamic Programming

Memoization

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

Example

Memoization with fibonacci problem.

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

Related

• Tabulation