Dynamic Programming

Question 1

What is memoization?

Answer 1

Memoization is a specific form of caching that involves caching the return value of a function based on its parameters.

Question 2

What are the two components of dynamic programming?

Answer 2

Solving a problem using divide and conquer (recursion) and memoization (caching results)

Question 3

How do you identify if a problem can be optimized with dynamic programming?

Answer 3

1. Can it be divided into subproblems?
2. Are the subproblems repetitive?

If so then, dynamic programming is perfect

Question 4

What is the trade off when using memoization?

Answer 4

You now have to hold a cache of values which increases space complexity