Dynamic Programming Concepts

Question 1

Optimal Substructure

Answer 1

When the optimal solution to a problem consists of optimal solutions to subproblems.

Question 2

Overlapping Subproblems

Answer 2

When breaking a problem into subproblems produces multiple instances of the same subproblem. i.e. Subproblems share subproblems

Question 3

Memoization

Answer 3

Storing optimal solutions to subproblems in order to solve dependant problems.

Question 4

Top-Down Solution

Answer 4

Recurses down to subproblems with trivial solutions, then memoizes results to solve subproblems all the way up the recursion stack.

Question 5

Bottom-Up Solution

Answer 5

Builds memoization table starting from basic trivial solutions until the desired solution is reached.