Recursion and Dynamic Programming

Question 1

Overlapping Subproblems (Dynamic Programming)

Answer 1

When finding a problem’s solution involves solving the same subproblem multiple times.

Examples:
* Fibonacci Sequence

Question 2

Memoization

Answer 2

Ensures that a method doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually a hash)

Memoization is a common strategy for dynamic programming problems

However, going bottom-up is usually cleaner and often more efficient.

Question 3

Bottom-up Algorithms

Answer 3

“Starts from the beginning”

as opposed to recursion which often starts from the end and works backwards.

Bottom-up is a way to avoid recursion, saving memory cost that recursion incurs when it builds up the call stack.